单调栈

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

例题

进阶指南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;
}

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/74/