【poj2559】Largest Rectangle in a Histogram

/*
    维护一个栈中元素(高度)单调递增的栈 
    扫描每个矩形，若比栈顶元素高就直接进栈
    否则弹出栈顶，直至递增，弹栈过程中累计弹出元素的宽度和，每弹出一个就用弹出高度*累计宽度更新答案。
    最后给当前矩形的宽度加上累计宽度，入栈。
    扫描结束后，依次弹出栈顶元素，按相同方法更新答案，直至栈为空 
*/
#include<cstdio>
#include<iostream>
using namespace std;
long long h[100010];
struct node
{
    long long hei,wid;
}stack[100010];
int n,head=0;
long long widsum=0,ans=0;
int main()
{
    while (scanf("%d",&n) && n)
    {
        ans=0;    head=0;    stack[head].hei=-1;
        for (int i=1;i<=n;i++)    
        scanf("%lld",&h[i]);
        h[++n]=0;
        for (int i=1;i<=n;i++)
        {
            if (h[i]>=stack[head].hei)//大于栈顶元素，直接入栈 
            {
                stack[++head].hei=h[i];
                stack[head].wid=1;
            }
            else
            {
                widsum=0;
                while (stack[head].hei>h[i])//不断弹出栈顶元素 直至递增 
                {
                    widsum+=stack[head--].wid;
                    ans=max(ans,stack[head+1].hei*widsum);//用弹出高度*累计宽度更新答案 
                }
                stack[++head].hei=h[i];
                stack[head].wid=widsum+1;//给当前矩形的宽度加上累计宽度入栈 
            }
        }
        printf("%lld\n",ans);
    }
}