【poj 2559 Largest Rectangle in a Histogram】【单调栈】

【链接】

http://poj.org/problem?id=2559

【题意】

在一条水平线上有若干紧挨的矩形，求包含于这些矩形的并集内部的最大的矩形的面积（矩形个数<=1e5）

【分析】我们先考虑，若矩形的高度从左往右单调递增，那么答案显而易见尝试以每个矩形的高度为最终矩形的高度，并把宽度延伸到右边界，得到一个矩形，取最大。如果下一个矩形的高度比上一个小，那么该矩形想贡献的话，这个矩形的面积的高度不可能超过比自己高度，换句话说，对于之前高度大于当前矩形的高度的，高于部分已经没有用了。用单调栈维护

【代码】

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
int a[maxn];
int sta[maxn];
int w[maxn];int main() {int n;while (~scanf("%d", &n),n) {memset(sta, 0, sizeof(sta));for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}a[n + 1] = 0;int top = 0;ll ans = 0;for (int i = 1; i <= n+1; i++) {if (a[i] > sta[top]) {sta[++top] = a[i];w[top] = 1;}else {int width = 0;while (sta[top] > a[i]) {width += w[top];ans = max(ans, (long long)width*sta[top]);top--;}sta[++top] = a[i];w[top] = width+1;}}printf("%lld\n", ans);}
}