单调栈

保持栈中元素的高度有效性和秩序性，及时排除无效的策略，以降低时间复杂度

例题

进阶指南P51-53

代码

#include <bits/stdc++.h>
using namespace std;

struct node{
    int h,w;
}tmp;
int n,h[100005];
long long ans;
stack <node> s;

int main(){
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",&h[i]);
    for (int i=1;i<=n+1;++i){
        int sum=0;
        while (!s.empty()&&s.top().h>h[i]){
            tmp=s.top();
            sum+=tmp.w;
            ans=max(ans,(long long)sum*tmp.h);
            s.pop();
        }
        tmp.h=h[i],tmp.w=sum+1;
        s.push(tmp);
    }
    cout<<ans<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/74/