http://poj.org/problem?id=2559
单调栈，就是具有单调性的栈。
本题你只要维护栈的单调性即可。每个矩形入栈时，判断它的高度是否大于等于栈顶矩形的高度，如果满足，则直接入栈。否则就向前找，一边出栈一边记录宽度，计算面积。知道找到第一个不满足条件的位置，然后将当前高度入栈。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,top,cnt,h[100035],p[100035],w[100035];
long long ans;
int main()
{
scanf("%d",&n);
while (n)
{
top=0;
ans=0LL;
for (int i=1;i<=n+1;i++)
{
if (i!=n+1) scanf("%d",&h[i]);else h[i]=0;
if (h[i]>=p[top]) p[++top]=h[i],w[top]=1;
else
{
int wide=0;
while (h[i]<p[top]&&top>0)
{
wide+=w[top];
ans=max(ans,(long long)wide*p[top]);
top--;
}
p[++top]=h[i];w[top]=wide+1;
}
}
printf("%lld\n",ans);
scanf("%d",&n);
}
}
