单调栈
单调栈
保持栈中元素的高度有效性和秩序性,及时排除无效的策略,以降低时间复杂度
例题
进阶指南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/