AcWing 3194. 最大的矩形（单调栈变形）

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
stack<int>s;
int n,a[N],ans,l[N],r[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        while(s.size()&&a[s.top()]>=a[i])s.pop();
        if(s.size())l[i]=s.top();
        else l[i]=0;
        s.push(i);
    }
    while(s.size())s.pop();
    reverse(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        while(s.size()&&a[s.top()]>=a[i])s.pop();
        if(s.size())r[i]=s.top();
        else r[i]=0;
        s.push(i);
    }
    reverse(a+1,a+1+n);
    for(int i=1,j=n;i<=n;i++,j--){
        ans=max(ans,(n-r[j]-l[i])*a[i]);
        //cout<<l[i]<<" "<<r[j]<<" "<<endl;
    }
    cout<<ans<<endl;
}