#8781. 最大的矩形
最大的矩形
Background
|
问题描述在横轴上放了n个相邻的矩形,|
每个矩形的宽度是1,而第i(1 ≤ i ≤ n)个矩形的高度是h~i~。这n个矩形构成了一个直方图。例如,下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。 |
请找出能放在给定直方图里面积最大的矩形,|
它的边要与坐标轴平行。|
对于上面给出的例子,最大矩形如下图所示的阴影部分,面积是10。
输入格式
|
第一行包含一个整数n,即矩形的数量(1 ≤ n ≤ 1000)。
|
第二行包含n 个整数h~1~, h~2~, … , h~n~,相邻的数之间由空格分隔。(1 ≤ h~i~ ≤ 10000)。h~i~是第i个矩形的高度。
|
输出格式
输出一行,包含一个整数,即给定直方图内的最大矩|
形的面积。
|
样例输入
|
6
|
3 1 6 5 2 3
|
样例输出
|
10
问题分析:
解决这个问题有两种方法,一是暴力法(枚举法),任何一个矩形必然始于第i个直方图,终止于第j块直方图(i<=j),从所有这些面积中找出最大矩形面积即可;二是对这n个数只看一遍,就算出最大矩形面积,其计算复杂度为O(n),相比较而言,算法要复杂一些,还需要付出空间的代价。仔细观察这两个算法有关的程序,会发现其实二者之间算法复杂度的差异很小。
后一种方法的基本思想是先找到一个逐步递增的面积,即如果Hi<Hi+1则最大面积是逐步递增的。这个过程中,将这些Hi放入堆栈中,直到不满足Hi<Hi+1为止。这个时候,最大的面积可能是最右边是Hi,由若干块(也可能只有1块)拼成的,从中获得一个最大的面积。出现面积非递增时,则把堆栈中比当前高的直方图弹出,重复上述过程,需要说明的是这不影响高的直方图与其右边连成一片。还有一点就是,所有的直方图的高度Hi>=1,这是一个前提,如果有的直方图高度为0,则这个算法需要另外设计。
程序说明:
对于暴力法来说,数据用数组来存储。另外一种数据存储方法是使用STL的包装类vector,可以实现动态数据存储,不受限于数据的多少。
Limitation
1s, 1024KiB for each test case.