[POJ 2559][Stack] Largest Rectangle in a Histogram

原題連結
無聊來刷刷水題......

如果我們在位置i，高度h[i]，包括i的矩形往左最多可以延伸到多左邊呢？
答案是延伸到第一個高度比我還要小的位置+1，我們將他稱為最佳左位置
怎麼快速作到這件事情？
若我們從左掃到右，首先觀察到當某個h[i]<h[j]且i>j，那麼其實j已經不可能是最佳左位置了。如果不能接受的可以看一下前面紅字。
所以我們維護一個堆疊，裡面放的是還有可能成為最佳左位置的人，顯然裡面的高度應該是單調遞增的。
如何更新？每當掃過1個i，從堆疊的頂端開始，把所有h比h[i]大的人刪掉。
由於每個位置最多只會進出堆疊1次，總複雜度是O(n)。
會算最佳左位置，就會算最佳右位置。
最後再花O(n)統計答案。

#define LL long long
#include<cstdio>
#include<stack>
using namespace std;
const LL maxn=100000+5;
LL a[maxn],L[maxn],R[maxn];
int main()
{
    stack<int> S;
    LL n;
    while(scanf("%lld",&n)==1 && n)
    {
        for(LL i=0;i<n;i++) scanf("%lld",a+i);
        while(!S.empty()) S.pop();
        for(LL i=0;i<n;i++)
        {
            while(!S.empty() && a[i]<=a[S.top()]) S.pop();
            if(S.empty()) L[i]=0;
            else L[i]=S.top()+1;
            S.push(i);
        }
        while(!S.empty()) S.pop();
        for(LL i=n-1;i>=0;i--)
        {
            while(!S.empty() && a[i]<=a[S.top()]) S.pop();
            if(S.empty()) R[i]=n-1;
            else R[i]=S.top()-1;
            S.push(i);
        }
        LL ans=0;
        for(LL i=0;i<n;i++) ans=max(ans,(R[i]-L[i]+1)*a[i]);
        printf("%lld\n",ans);
    }
}