[poj 2559] Largest Rectangle in a Histogram：单调栈

题意：求直方图中矩形的最大面积。

从左往右扫描，用栈维护左边所有可用的高度。高度是递增的，因为，如果$i>j$且$h_i<h_j$，$j$一定优于$i$。如果当前实际高度不矮于栈顶，那么会有些高度从现在开始不可用。更新答案，剔除它们，以当前高度为可用高度，横坐标尽可能小，压入栈中。

换言之，用单调栈维护每个横坐标左、右比它矮的最近的位置。原本需要从左往右、从右往左各做一次，针对此问题，可通过加入以前的横坐标进行优化，只往一边扫。

#include <cstdio>
#include <stack>
using namespace std;
typedef long long ll;
struct Node {int x, y;
};
inline int read()
{int x = 0; char ch = getchar();while (ch<'0' || ch>'9') ch = getchar();while (ch>='0' && ch<='9') {x = x*10 + ch - '0';ch = getchar();}return x;
}int main()
{int n;while (n=read()) {stack<Node> S;ll ans = 0;for (int i = 0; i <= n; ++i) {int y = 0;if (i != n)y = read();Node t = (Node){i};while (!S.empty() && S.top().y >= y) {t = S.top();ans = max(ans, ll(i-t.x)*t.y);S.pop();}t.y = y;S.push(t);}printf("%lld\n", ans);}return 0;
}