单调栈

SP1805

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#define maxn 100010
#define ll long long
using namespace std;
template<typename T>
inline void read(T &x){
    x=0;bool flag=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
    for(;isdigit(c);c=getchar()) x=x*10+(c^48);
    if(flag) x=-x;
}

ll n,h[maxn],l[maxn],r[maxn],len[maxn];
ll s[maxn],ans;

int main(){
    while(1){
        read(n);
        if(n==0) return 0;
        for(int i=1;i<=n;i++) read(h[i]);
        for(int i=1;i<=n;i++) l[i]=i,r[i]=i;
        r[n+1]=n+1;
        ans=0;
        for(int i=1;i<=n;i++){
            while((l[i]-1>=1)&&(h[l[i]-1]>=h[i]))
                l[i]=l[l[i]-1];
        }
        for(int i=n;i>=1;i--){
            while((r[i]+1<=n)&&(h[r[i]+1]>=h[i]))
                r[i]=r[r[i]+1];
            len[i]=r[i]-l[i]+1;
        }
        for(int i=1;i<=n;i++)
            ans=max(ans,h[i]*len[i]);
        cout<<ans<<endl;
    }
    return 0;
} 

其实大概没写蓝书上的板子