Largest Rectangle in a Histogram
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1012 Accepted Submission(s): 335
Problem Description
A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:
Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.
Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.
Input
The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, ..., hn, where 0 <= hi <= 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.
Output
For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.
Sample Input
7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0
Sample Output
8 4000
#include<stdio.h> #define M 100005 int n,i,l[M],r[M]; long long max,term,p[M]; int main() { while(scanf("%d",&n),n) { p[0]=p[n+1]=max=-1; for(i=1;i<=n;i++) { l[i]=r[i]=i; scanf("%lld",&p[i]); } for(i=n;i>=1;i--)while(p[i]<=p[r[i]+1])r[i]=r[r[i]+1]; for(i=1;i<=n;i++)while(p[l[i]-1]>=p[i])l[i]=l[l[i]-1]; for(i=1;i<=n;i++) { term=p[i]*(r[i]-l[i]+1); if(max<term)max=term; } printf("%lld\n",max); } return(0); }
相关推荐
LeetCode题目Largest Rectangle in Histogram 解答
LintCode - 122. Largest Rectangle in Histogram(直方图最大矩形覆盖)(单调栈)题目链接题目解析主要是运用单调栈(单
http://blog.csdn.net/two_water/article/details/53004027 LeetCode_直方图最大面积(Largest Rectangle in Histogram)
1,求直方图中最大矩形的面积。 上面是一个直方图,其中每个条的宽度为 1,给定高度 = [2,1,5,6,2,3]。 最大的矩形显示在阴影区域中,其面积 = 10 单位。 实现 1:O(n^2) class Solution { public int ...
实现利用Rectangle输出一个矩形的周长和面积
c++经典程序 北邮c++实验课老师留的作业
java 实验 继承与多态rectAngle 定义矩形类,用户输入矩形的长与宽,程序计算其面积和周长;派生子类正方形类,定义一个接口Printable源代码
定义一个名为rectangle 的矩形类,其属性数据为矩形左上角和右上角的点的坐标能计算矩形的面积
java代码-编写一个类,类名为Rectangle(矩形),它有两个...有一个方法area(),没有参数,返回类型为double,功能是求矩形的面积;还有另一个方法为perimeter()没有参数,返回类型为double,功能是求矩形的周长,
1.建立一个形状类Shape作为基类,派生出圆类Circle和矩形类Rectangle,求出面积并获取相关信息。 具体要求如下: (1)形状类Shape (a)保护数据成员 double x,y:对于不同的形状,x和y表示不同的含义,如对于圆,...
本代码主要利用MATLAB工具实现MATLAB——使用rectangle命令创建二维矩形或椭圆区域,简单明了,易于理解
矩形面积计算,c++实现,rectangle的大小
按以下描述和要求建立两个类:基类 Rectangle(矩形类) 和派生类 Cube(正方体) 1. Rectangle 私有成员: double x1, y1; //左下角的坐标 double x2, y2; //右上角的坐标 公有成员: 带缺省值的构造...
x 和 y 坐标点数组四个角点的矩形数组算法中使用precision来比较矩形的面积和点与矩形组成的三角形和,默认为6 例子 var checkPoint = require ( 'check-point-in-rectangle' ) ; if ( checkPoint ( [ 5 , 5 ] , [ ...
C#-矩形-Rectangle
1.创建一个类Rectangle,已知a、b求面积,求三角形的面积 2.结合题目一,从题目一文件中读取数据,并采用类的方法,将计算的结果写在另一个文档中。 (1)利用类进行计算一个矩形的面积,已经a、b边长。 class ...
// create rectangles with the Rectangle class://// new Rectangle(x, y, width, height)// create a 2x2 rectangle at 1,1var rect1 = new Rectangle ( 1 , 1 , 2 , 2 ) ;// check if the rect contains a point...