首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >最大的矩形

最大的矩形

作者头像
geekfly
发布于 2022-05-06 11:23:48
发布于 2022-05-06 11:23:48
56800
代码可运行
举报
文章被收录于专栏:geekflygeekfly
运行总次数:0
代码可运行

问题描述 试题编号: 201312-3 试题名称: 最大的矩形 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   在横轴上放了n个相邻的矩形,每个矩形的宽度是1,而第i(1 ≤ i ≤ n)个矩形的高度是hi。这n个矩形构成了一个直方图。

  请找出能放在给定直方图里面积最大的矩形,它的边要与坐标轴平行。对于上面给出的例子,最大矩形如下图所示的阴影部分,面积是10。 输入格式   第一行包含一个整数n,即矩形的数量(1 ≤ n ≤ 1000)。   第二行包含n 个整数h1, h2, … , hn,相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。 输出格式   输出一行,包含一个整数,即给定直方图内的最大矩形的面积。 样例输入 6 3 1 6 5 2 3 样例输出 10

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
package geekfly.test;

import java.util.Scanner;

public class 最大的矩形 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] arr = new int[num];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        int area = 0;
        for(int i=0;i<num;i++){
            int higth = arr[i],width=1;
            for(int x=i-1;x>=0;x--){
                if(arr[x]<arr[i])
                    break;
                width++;
            }
            for(int y=i+1;y<num;y++){
                if(arr[y]<arr[i])
                    break;
                width++;
            }
            if(area<width*arr[i])
                area = width*arr[i];
        }
        System.out.println(area);

    }

}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-04-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
201312-3
试题编号: 201312-3 试题名称: 最大的矩形 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   在横轴上放了n个相邻的矩形,每个矩形的宽度是1,而第i(1 ≤ i ≤ n)个矩形的高度是hi。这n个矩形构成了一个直方图。例如,下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。
Max超
2019/01/21
4350
试题 基础练习 字母图形
资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 利用字母可以组成一些美丽的图形,下面给出了一个例子: ABCDEFG BABCDEF CBABCDE DCBABCD EDCBABC 这是一个5行7列的图形,请找出这个图形的规律,并输出一个n行m列的图形。 输入格式 输入一行,包含两个整数n和m,分别表示你要输出的图形的行数的列数。 输出格式 输出n行,每个m个字符,为你的图形。 样例输入 5 7 样例输出 ABCDEFG BABCDEF CBABCDE DCBABCD EDCBABC
SingYi
2022/07/13
1640
消除类游戏
问题描述 试题编号: 201512-2 试题名称: 消除类游戏 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   消除类游戏是深受大众欢迎的一种游戏,游戏在一个包含有n行m列的游戏棋盘上进行,棋盘的每一行每一列的方格上放着一个有颜色的棋子,当一行或一列上有连续三个或更多的相同颜色的棋子时,这些棋子都被消除。当有多处可以被消除时,这些地方的棋子将同时被消除。   现在给你一个n行m列的棋盘,棋盘中的每一个方格上有一个棋子,请给出经过一次消除后的棋盘。   请注意:一个棋子可能在某一行和某一列同时被消除。 输入格式   输入的第一行包含两个整数n, m,用空格分隔,分别表示棋盘的行数和列数。   接下来n行,每行m个整数,用空格分隔,分别表示每一个方格中的棋子的颜色。颜色使用1至9编号。 输出格式   输出n行,每行m个整数,相邻的整数之间使用一个空格分隔,表示经过一次消除后的棋盘。如果一个方格中的棋子被消除,则对应的方格输出0,否则输出棋子的颜色编号。 样例输入 4 5 2 2 3 1 2 3 4 5 1 4 2 3 2 1 3 2 2 2 4 4 样例输出 2 2 3 0 2 3 4 5 0 4 2 3 2 0 3 0 0 0 4 4 样例说明   棋盘中第4列的1和第4行的2可以被消除,其他的方格中的棋子均保留。 样例输入 4 5 2 2 3 1 2 3 1 1 1 1 2 3 2 1 3 2 2 3 3 3 样例输出 2 2 3 0 2 3 0 0 0 0 2 3 2 0 3 2 2 0 0 0 样例说明   棋盘中所有的1以及最后一行的3可以被同时消除,其他的方格中的棋子均保留。 评测用例规模与约定   所有的评测用例满足:1 ≤ n, m ≤ 30。
geekfly
2022/05/06
5070
出现次数最多的数
问题描述 试题编号: 201312-1 试题名称: 出现次数最多的数 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   给定n个正整数,找出它们中出现次数最多的数。如果这样的数有多个,请输出其中最小的一个。 输入格式   输入的第一行只有一个正整数n(1 ≤ n ≤ 1000),表示数字的个数。   输入的第二行有n个整数s1, s2, …, sn (1 ≤ si ≤ 10000, 1 ≤ i ≤ n)。相邻的数用空格分隔。 输出格式   输出这n个次数中出现次数最多的数。如果这样的数有多个,输出其中最小的一个。 样例输入 6 10 1 10 20 30 20 样例输出 10
geekfly
2022/05/06
5610
蓝桥杯vip测试题系统-数组求和(解题思路以及解题代码,手画思路图虽然丑丑的)
资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   输入n个数,围成一圈,求连续m(m<n)个数的和最大为多少? 输入格式   输入的第一行包含两个整数n, m。第二行,共n个
手撕代码八百里
2020/07/28
3200
相邻整数
问题描述 试题编号: 201409-1 试题名称: 相邻数对 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   给定n个不同的整数,问这些数中有多少对整数,它们的值正好相差1。 输入格式   输入的第一行包含一个整数n,表示给定整数的个数。   第二行包含所给定的n个整数。 输出格式   输出一个整数,表示值正好相差1的数对的个数。 样例输入 6 10 2 6 3 7 8 样例输出 3 样例说明   值正好相差1的数对包括(2, 3), (6, 7), (7, 8)。 评测用例规模与约定   1<=n<=1000,给定的整数为不超过10000的非负整数。
geekfly
2022/05/06
4330
数字排序
问题描述 试题编号: 201503-2 试题名称: 数字排序 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   给定n个整数,请统计出每个整数出现的次数,按出现次数从多到少的顺序输出。 输入格式   输入的第一行包含一个整数n,表示给定数字的个数。   第二行包含n个整数,相邻的整数之间用一个空格分隔,表示所给定的整数。 输出格式   输出多行,每行包含两个整数,分别表示一个给定的整数和它出现的次数。按出现次数递减的顺序输出。如果两个整数出现的次数一样多,则先输出值较小的,然后输出值较大的。 样例输入 12 5 2 3 3 1 3 4 2 5 2 3 5 样例输出 3 4 2 3 5 3 1 1 4 1 评测用例规模与约定   1 ≤ n ≤ 1000,给出的数都是不超过1000的非负整数。
geekfly
2022/05/06
4570
试题 算法训练 二进制数数
  给定L,R。统计[L,R]区间内的所有数在二进制下包含的“1”的个数之和。   如5的二进制为101,包含2个“1”。
SingYi
2022/07/13
2250
节日
问题描述 试题编号: 201503-3 试题名称: 节日 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   有一类节日的日期并不是固定的,而是以“a月的第b个星期c”的形式定下来的,比如说母亲节就定为每年的五月的第二个星期日。   现在,给你a,b,c和y1, y2(1850 ≤ y1, y2 ≤ 2050),希望你输出从公元y1年到公元y2年间的每年的a月的第b个星期c的日期。   提示:关于闰年的规则:年份是400的整数倍时是闰年,否则年份是4的倍数并且不是100的倍数时是闰年,其他年份都不是闰年。例如1900年就不是闰年,而2000年是闰年。   为了方便你推算,已知1850年1月1日是星期二。 输入格式   输入包含恰好一行,有五个整数a, b, c, y1, y2。其中c=1, 2, ……, 6, 7分别表示星期一、二、……、六、日。 输出格式   对于y1和y2之间的每一个年份,包括y1和y2,按照年份从小到大的顺序输出一行。   如果该年的a月第b个星期c确实存在,则以”yyyy/mm/dd”的格式输出,即输出四位数的年份,两位数的月份,两位数的日期,中间用斜杠“/”分隔,位数不足时前补零。   如果该年的a月第b个星期c并不存在,则输出”none”(不包含双引号)。 样例输入 5 2 7 2014 2015 样例输出 2014/05/11 2015/05/10 评测用例规模与约定   所有评测用例都满足:1 ≤ a ≤ 12,1 ≤ b ≤ 5,1 ≤ c ≤ 7,1850 ≤ y1, y2 ≤ 2050。 本题目提交分数为80分。
geekfly
2022/05/06
2830
模板生成系统
问题描述 试题编号: 201509-3 试题名称: 模板生成系统 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   成成最近在搭建一个网站,其中一些页面的部分内容来自数据库中不同的数据记录,但是页面的基本结构是相同的。例如,对于展示用户信息的页面,当用户为 Tom 时,网页的源代码   而当用户为 Jerry 时,网页的源代码
geekfly
2022/05/06
6550
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-基础练习 查找整数
        最近的一些文章都可能会很碎,写到哪里是哪里,过一阵子会具体的整理一遍,这里其它的类型题先往后排一排,因为蓝桥最后考的也就是对题目逻辑的理解能力,也就是dp分析能力了,所以就主要目标定在这里,最近的题目会很散,很多,基本上都是网罗全网的一些dp练习题进行二次训练,准备比赛的学生底子薄的先不建议看啊,当然,脑子快的例外,可以直接跳过之前的一切直接来看即可,只需要你在高中的时候数学成绩还可以那就没啥问题,其实,dp就是规律总结,我们只需要推导出对应题目的数学规律就可以直接操作,可能是一维数组,也可能是二维数组,总体来看二维数组的较多,但是如果能降为的话建议降为,因为如果降为起来你看看时间复杂度就知道咋回事了,那么在这里祝大家能无序的各种看明白,争取能帮助到大家。
红目香薰
2023/02/17
2650
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-基础练习 查找整数
201312-3 最大的矩形(Python)
https://blog.aksy.space/CCF-CSP/201312-3.html
用户5654806
2020/09/25
1.2K0
数列分段题目
问题描述 试题编号: 201509-1 试题名称: 数列分段 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   给定一个整数数列,数列中连续相同的最长整数序列算成一段,问数列中共有多少段? 输入格式   输入的第一行包含一个整数n,表示数列中整数的个数。   第二行包含n个整数a1, a2, …, an,表示给定的数列,相邻的整数之间用一个空格分隔。 输出格式   输出一个整数,表示给定的数列有多个段。 样例输入 8 8 8 8 0 12 12 8 0 样例输出 5 样例说明   8 8 8是第一段,0是第二段,12 12是第三段,倒数第二个整数8是第四段,最后一个0是第五段。 评测用例规模与约定   1 ≤ n ≤ 1000,0 ≤ ai ≤ 1000。
geekfly
2022/08/11
7120
相反数
问题描述 试题编号: 201403-1 试题名称: 相反数 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   有 N 个非零且各不相同的整数。请你编一个程序求出它们中有多少对相反数(a 和 -a 为一对相反数)。 输入格式   第一行包含一个正整数 N。(1 ≤ N ≤ 500)。   第二行为 N 个用单个空格隔开的非零整数,每个数的绝对值不超过1000,保证这些整数各不相同。 输出格式   只输出一个整数,即这 N 个数中包含多少对相反数。 样例输入 5 1 2 3 -1 -2 样例输出 2
geekfly
2022/05/06
4440
字符串匹配
问题描述 试题编号: 201409-3 试题名称: 字符串匹配 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   给出一个字符串和多行文字,在这些文字中找到字符串出现的那些行。你的程序还需支持大小写敏感选项:当选项打开时,表示同一个字母的大写和小写看作不同的字符;当选项关闭时,表示同一个字母的大写和小写看作相同的字符。 输入格式   输入的第一行包含一个字符串S,由大小写英文字母组成。   第二行包含一个数字,表示大小写敏感的选项,当数字为0时表示大小写不敏感,当数字为1时表示大小写敏感。   第三行包含一个整数n,表示给出的文字的行数。   接下来n行,每行包含一个字符串,字符串由大小写英文字母组成,不含空格和其他字符。 输出格式   输出多行,每行包含一个字符串,按出现的顺序依次给出那些包含了字符串S的行。 样例输入 Hello 1 5 HelloWorld HiHiHelloHiHi GrepIsAGreatTool HELLO HELLOisNOTHello 样例输出 HelloWorld HiHiHelloHiHi HELLOisNOTHello 样例说明   在上面的样例中,第四个字符串虽然也是Hello,但是大小写不正确。如果将输入的第二行改为0,则第四个字符串应该输出。 评测用例规模与约定   1<=n<=100,每个字符串的长度不超过100。
geekfly
2022/05/06
1K0
数位之和
问题描述 试题编号: 201512-1 试题名称: 数位之和 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   给定一个十进制整数n,输出n的各位数字之和。 输入格式   输入一个整数n。 输出格式   输出一个整数,表示答案。 样例输入 20151220 样例输出 13 样例说明   20151220的各位数字之和为2+0+1+5+1+2+2+0=13。 评测用例规模与约定   所有评测用例满足:0 ≤ n ≤ 1000000000。
geekfly
2022/05/06
2200
门禁系统
问题描述 试题编号: 201412-1 试题名称: 门禁系统 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   涛涛最近要负责图书馆的管理工作,需要记录下每天读者的到访情况。每位读者有一个编号,每条记录用读者的编号来表示。给出读者的来访记录,请问每一条记录中的读者是第几次出现。 输入格式   输入的第一行包含一个整数n,表示涛涛的记录条数。   第二行包含n个整数,依次表示涛涛的记录中每位读者的编号。 输出格式   输出一行,包含n个整数,由空格分隔,依次表示每条记录中的读者编号是第几次出现。 样例输入 5 1 2 1 1 3 样例输出 1 1 2 3 1 评测用例规模与约定   1≤n≤1,000,读者的编号为不超过n的正整数。
geekfly
2022/05/06
4350
窗口
问题描述 试题编号: 201403-2 试题名称: 窗口 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   在某图形操作系统中,有 N 个窗口,每个窗口都是一个两边与坐标轴分别平行的矩形区域。窗口的边界上的点也属于该窗口。窗口之间有层次的区别,在多于一个窗口重叠的区域里,只会显示位于顶层的窗口里的内容。   当你点击屏幕上一个点的时候,你就选择了处于被点击位置的最顶层窗口,并且这个窗口就会被移到所有窗口的最顶层,而剩余的窗口的层次顺序不变。如果你点击的位置不属于任何窗口,则系统会忽略你这次点击。   现在我们希望你写一个程序模拟点击窗口的过程。 输入格式   输入的第一行有两个正整数,即 N 和 M。(1 ≤ N ≤ 10,1 ≤ M ≤ 10)   接下来 N 行按照从最下层到最顶层的顺序给出 N 个窗口的位置。 每行包含四个非负整数 x1, y1, x2, y2,表示该窗口的一对顶点坐标分别为 (x1, y1) 和 (x2, y2)。保证 x1 < x2,y1 2。   接下来 M 行每行包含两个非负整数 x, y,表示一次鼠标点击的坐标。   题目中涉及到的所有点和矩形的顶点的 x, y 坐标分别不超过 2559 和  1439。 输出格式   输出包括 M 行,每一行表示一次鼠标点击的结果。如果该次鼠标点击选择了一个窗口,则输出这个窗口的编号(窗口按照输入中的顺序从 1 编号到 N);如果没有,则输出”IGNORED”(不含双引号)。 样例输入 3 4 0 0 4 4 1 1 5 5 2 2 6 6 1 1 0 0 4 4 0 5 样例输出 2 1 1 IGNORED 样例说明   第一次点击的位置同时属于第 1 和第 2 个窗口,但是由于第 2 个窗口在上面,它被选择并且被置于顶层。   第二次点击的位置只属于第 1 个窗口,因此该次点击选择了此窗口并将其置于顶层。现在的三个窗口的层次关系与初始状态恰好相反了。   第三次点击的位置同时属于三个窗口的范围,但是由于现在第 1 个窗口处于顶层,它被选择。   最后点击的 (0, 5) 不属于任何窗口。
geekfly
2022/05/06
9020
Java 01背包【动态规划·蓝桥杯练习题】(相信杨超越,相信锦鲤,默默努力,其它的看天意)
时间限制:1.0s 内存限制:256.0MB 关键字:01背包 动态规划 问题描述   金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的N元。于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过N元(可以等于N元)的前提 下,使每件物品的价格与重要度的乘积的总和最大。   设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为 j1,j2,……,jk,则所求的总和为:   v[j1]w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。(其中为乘号)   请 你帮助金明设计一个满足要求的购物单。 输入格式   输入文件 的第1行,为两个正整数,用一个空格隔开:   N m   (其中N(<30000)表示总钱 数,m(<25)为希望购买物品的个数。)   从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有2个非负整数   v p   (其中v表示该物品的价格(v<=10000),p表示该物品的重要度(1~5)) 输出格式   输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。 样例输入 1000 5 800 2 400 5 300 5 400 3 200 2 样例输出 3900
红目香薰
2022/11/28
2370
日期计算
问题描述 试题编号: 201509-2 试题名称: 日期计算 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   给定一个年份y和一个整数d,问这一年的第d天是几月几日?   注意闰年的2月有29天。满足下面条件之一的是闰年:   1) 年份是4的整数倍,而且不是100的整数倍;   2) 年份是400的整数倍。 输入格式   输入的第一行包含一个整数y,表示年份,年份在1900到2015之间(包含1900和2015)。   输入的第二行包含一个整数d,d在1至365之间。 输出格式   输出两行,每行一个整数,分别表示答案的月份和日期。 样例输入 2015 80 样例输出 3 21 样例输入 2000 40 样例输出 2 9
geekfly
2022/05/06
8330
相关推荐
201312-3
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档