题意
直方图是由在公共基线处对齐的一系列矩形组成的多边形。
矩形具有相等的宽度,但可以具有不同的高度。
例如,图例左侧显示了由高度为2,1,4,5,1,3,3的矩形组成的直方图,矩形的宽度都为1:
通常,直方图用于表示离散分布,例如,文本中字符的频率。
现在,请你计算在公共基线处对齐的直方图中最大矩形的面积。
图例右图显示了所描绘直方图的最大对齐矩形。
输入格式
输入包含几个测试用例。
每个测试用例占据一行,用以描述一个直方图,并以整数n开始,表示组成直方图的矩形数目。
然后跟随n个整数$h_1,h_2....h_n$
这些数字以从左到右的顺序表示直方图的各个矩形的高度。
每个矩形的宽度为1。
同行数字用空格隔开。
当输入用例为n=0时,结束输入,且该用例不用考虑。
输出格式
对于每一个测试用例,输出一个整数,代表指定直方图中最大矩形的区域面积。
每个数据占一行。
请注意,此矩形必须在公共基线处对齐。
数据范围
1≤n≤100000
0≤hi≤1000000000
输入样例:
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
输出样例:
8
4000
分析
使用单调栈。
如果添加当前矩形的高度,栈仍然保持单调递增,就将其放入栈中。
否则弹出比当前数大的数,在这个过程中,同时计算弹出的矩形的宽度之和width,而当前被弹出的矩形的高度*width就是当前个矩形扩散所能达到的最大面积,弹出完毕时,将width+1作为新的矩形的宽度,并将其放入栈中,这个过程的结束意味着将当前矩形及其左边的所有可扩散目标化为一个矩形。最后添加添加一个矩形高度为0,保证所有矩形都被弹出 。
总而言之,弹出的过程在计算被弹出元素算右边的元素+左边元素(左边元素已经在入栈是被算出)之和,而弹出结果得到了当前新元素左边元素之和,所有元素被放入栈后只需要考虑右边的可扩散矩阵。
代码
#include <iostream>
#define N 100009
typedef long long ll;
using namespace std;
ll s[N];
int w[N],h,n;
int main() {
while (cin >> n && n) {
int top = 0;
s[top] = -1; w[top] = 0;
ll ans = 0;
for (int i = 0; i <= n; i++) {
if (i < n)
cin >> h;
else
h = 0;
if (h > s[top])
s[++top] = h, w[top] = 1;
else {
int width = 0;
while (h <= s[top]) {
//这里是弹出的过程,在这个过程中,当前h左边的相邻的比i大的会被累加
//而被弹出的数已经计算了左边,在比它大的数比它先弹出,宽度被累加在width中
width += w[top];
ans = max(ll(width) * s[top], ans);
top--;
}
s[++top] = h;
w[top] = ++width;
}
}
cout << ans << endl;
}
}