博客

Largest Rectangle in a Histogram

HDU – 1506

直方图是由在共同基线上排列的矩形序列组成的多边形。矩形具有相等的宽度，但可以具有不同的高度。例如，左边的图显示了由高度为2, 1, 4、5, 1, 3、3的矩形组成的直方图，其中单位为矩形的宽度为1：



通常，直方图用于表示离散分布，例如文本中字符的频率。请注意，矩形的顺序，即它们的高度，是重要的。在直方图中计算最大矩形的面积，该直方图也是在公共基线上对齐的。右边的图形显示了直方图中最大的对齐矩形。

Input

多组测试数据 每组测试数据的第一行为n(1 <= n <= 100000)， 表示图形有n个小矩形构成. 接下来一行输入n个整数h1, h2…hn (0 <= hi <= 1000000000, 1 <= i <= n), 表示每个小矩形的高度 n为0时程序结束

Output

仅输出一行表示面积的最大值

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8
4000

要求最大的矩形的面积.想一想可以得到最大面积就是从某一个矩形向两边扩展, 扩展的条件是左边或者右边的高度大于等于当前位置的高度. 这样就可以得到最大的面积

单调栈实现

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<string>
#include<stack>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 100000 + 100;
ll a[MAXN];
int L[MAXN], R[MAXN];
int main(){
	int n;
	while (scanf("%d", &n) != EOF && n){
		stack<int> s; s.push(0);
		ll ans = 0;
		for (int i = 1; i <= n + 1; i++){
			if (i <= n) scanf("%lld", &a[i]);
			else a[i] = 0;
			L[i] = R[i] = i;
			while (s.size() > 1 && a[s.top()] >= a[i]){//保证栈顶元素的下边没有大于自己的
				//如果a[栈顶元素] >= a[当前元素], 那么栈顶元素右边的第一个小于自己的就是这个元素
				R[s.top()] = i - 1;
				s.pop();
			}//循环保证有一个左边界
			L[i] = s.top();
			s.push(i);
		}
		for (int i = 1; i <= n; i++) ans = max(ans, (R[i] - L[i])*a[i]);
		printf("%lld\n", ans);
	}
#ifdef __wh
	system("pause");
#endif
	return 0;
}
//6 2 5 2 5 5 2