题解 | #Largest Rectangle in a Histogram#

单调栈AC代码+注释如下：

#include<iostream>
using namespace std;
#define int long long
const int N=100005;
int n,top,ans,a[N];
int sk[N],t;//栈

signed main(){
    while(cin>>n){
        if(n==0)return 0;
        ans=0;a[n]=-1;//初始化
        for(int i=0;i<n;i++)cin>>a[i];
        
        for(int i=0;i<=n;i++){
            if(!t||a[i]>=a[sk[t]])sk[++t]=i;//维护递增栈
            else{
                while(t&&a[sk[t]]>a[i]){//维护递增栈，如遇到比当前值大的出栈
                    int p=(i-sk[t])*a[sk[t]];//计算面积
                    ans=max(ans,p);//更新答案
                    t--;//出栈
                }
                a[sk[++t]]=a[i];    //将最后一次出栈位置的值改为当前最小值
                                    //依然为递增栈
            }
        }
        
        cout<<ans<<endl;
    }
}