#创作计划#单调栈
2025-01-19 20:58:06
发布于：浙江
12阅读
0回复
0点赞
应张子渝需求，现更新一篇单调栈和单调队列。（本篇只讲单调栈，单调队列还在更新）
所谓单调就是指元素按递增或递减的排列方式规整地排列。
例如
{}，
{}，
{}...
都属于按单调排列，而
{}，
{}，
{}...
则不属于按单调排列。
单调栈
何为单调栈？顾名思义，单调栈即满足单调性的栈结构。为了方便描述，接下来以从栈底到栈顶满足递增的单调栈举例。
现有一个单调栈，里面只有一个元素 。
接着将元素 压栈，因为 {} 仍符合递增，所以可以直接压栈。
如果接下来还要将元素 压栈，因为 {} 不符合递增关系，所以不可以直接压栈。为保证栈的单调性，需先把元素 弹出，再压入元素 。
另外如果我们要弹出元素，考虑到无论怎么弹，栈始终保持单调性（此处读者可自行理解），所以可直接弹出。
所以，单调栈基本代码应是这样的：
stack<int>s;
void pop(){
s.pop();//直接弹出
}
void push(int x){
while(!s.empty() && x>s.top()) pop();//先弹出所有小于x的元素
s.push(x);//再压栈
}
1.例题 【模板】单调栈
题目入口
该题是模板，今后注意到像“之后第一个大于”一类的字眼，可以考虑到单调栈。
该题 AC 代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,a[3000005],f[3000005];
stack<int>s;
void pop(){
s.pop();//直接弹出
}
void push(int idx){
while(!s.empty() && a[idx]>a[s.top()]) f[s.top()]=idx,pop();
//当元素y在讲元素x压入栈时被弹出，那么元素x一定是元素y向右找到的第一个大于元素y的元素，否则元素y一定在这之前就被弹出了（这里有些难理解，必要的话一定要自己画画图，否则将来会很吃力）
//和上述代码不同，此处单调栈中存的是元素下标，不是元素。
//所以第二个条件是x>a[s.top()]，不是x>as.top()。
s.push(idx);//最后压栈
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) push(i);//存入
while(!s.empty()) f[s.top()]=0,pop();//还留在栈中的/一定是向右找不到大于它自己/的元素(加了些停顿，便于理解)
for(int i=1;i<=n;i++) cout<<f[i]<<" ";//输出
return 0;
}
本题还可以用单调递减栈完成，现不一一展示。
有帮助，赞一个