POJ - 2559 单调栈

/*H E A D*/
int main(){
    int n,h[maxn],w[maxn];
    stack<int> stk;
    while(~iin(n)){
        if(n==0)break;
        rep(i,1,n) h[i]=read();
        while(!stk.empty()) stk.pop();
        h[n+1]=0;
        ll ans=0;
        rep(i,1,n+1){
            if(stk.empty()||stk.top()<h[i]){
                stk.push(h[i]);
                w[stk.size()]=1;
            }else{
                int width=0;
                while(!stk.empty()&&stk.top()>h[i]){
                    int t=stk.top();
                    width+=w[stk.size()];
                    stk.pop();
                    ans=max(ans,1ll*t*width);
                }
                stk.push(h[i]);
                w[stk.size()]=width+1;
            }
        }
        println(ans);
    }
    return 0;
}