题目链接

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

分析

单调栈，时刻保证栈内元素单调。

依次扫描每个矩形，若栈空或当前矩形高度不小于栈顶矩形，则直接将该长度为 $1$1 的矩形入栈；

若当前矩形高度小于栈顶矩形，则不断弹出栈顶，直至栈空或当前矩形高度不小于栈顶矩形；

每次新弹出的栈顶矩形一定不比之前弹出的矩形高，因此累加已弹出矩形的长度，再乘以新弹出矩形的高度即可更新答案；

弹完后将当前矩形的长度加上统计的弹出矩形的长度和，再入栈；

可自设第 $n + 1$n+1 个矩形，高度为 $0$0，保证最后栈空。

AC代码

#include <cstdio>
#include <algorithm>
#include <stack>

using namespace std;

inline int read() {
	int num = 0;
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9')
		num = num * 10 + c - '0', c = getchar();
	return num;
}

struct Rect {
	int h, w;

	Rect(int h, int w) : h(h), w(w) {}
};

stack<Rect> s;

int main() {
	int n;
	while (scanf("%d", &n) == 1 && n) {
		int h;
		long long ans = 0;
		for (int i = 1; i <= n + 1; ++i) {
			if (i <= n) h = read();
			else h = 0;
			if (s.empty() || h >= s.top().h) s.push(Rect(h, 1));
			else {
				int w = 0;
				while (!s.empty() && h < s.top().h) {
					w += s.top().w;
					ans = max(ans, 1ll * s.top().h * w);
					s.pop();
				}
				if (h) s.push(Rect(h, w + 1));
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}