淡谈单调栈/队列

pipilong2024 · 2025-06-30 13:45:45 · 算法·理论

何为单调

所谓单调就是指元素按递增或递减的排列方式规整地排列。
例如

{1,2,3,4,5,6}，
{1,2,5,10,12,16}，
{9,8,7,6,1,-1}...

都属于按单调排列，而

{1,2,7,4,5,6}，
{1,0,5,11,12,16}，
{9,8,17,6,1,-1}...

则不属于按单调排列。

单调栈

何为单调栈？顾名思义，单调栈即满足单调性的栈结构。为了方便描述，接下来以从栈底到栈顶满足递增的单调栈（即单调递增栈）举例。
现有一个单调栈，里面只有一个元素 5。

接着将元素 3 压栈，因为 {3,5} 仍符合递增，所以可以直接压栈。

如果接下来还要将元素 4 压栈，因为 {4,3,5} 不符合递增关系，所以不可以直接压栈。为保证栈的单调性，需先把元素 3 弹出，再压入元素 4。

另外如果我们要弹出元素，考虑到无论怎么弹，栈始终保持单调性（此处读者可自行理解），所以可直接弹出。

所以，单调栈基本代码应是这样的：

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;
}

本题还可以用单调递减栈完成，现不一一展示。

其他例题

P1901 P2866 P2947 B3666 P4147

单调队列

何为单调队列？顾名思义，单调队列即满足单调性的队列结构。为了方便描述，接下来以从队首到队尾满足递增的单调队列（即单调递增队列）举例。
现有一个单调队列，里面没有任何元素。
然后我把元素 3 加入队列，因为 {3} 符合递增关系，所以可以直接加入队列。

接着再把元素 5 加入队列，因为 {3,5} 仍符合递增关系，所以依旧可以直接加入队列。

可当如果我还要把元素 4 加入队列，因为 {3,5,4} 不符合递增关系，那么就不可以直接加入队列。为保证队列的单调性，需先把元素 {3，5} 依次弹出，再把元素 4 加入队列。

另外如果我们要弹出元素，考虑到同单调栈一样无论怎么弹，队列始终保持单调性（此处读者可自行理解），所以可直接弹出。

综上所述，单调队列基本代码应是这样的：

queue<int>q;
void pop(){
    q.pop();//直接弹出
}
void push(int x){
    while(q.size()&&q.back()>x) pop();
  //当发现有队尾比x大时，就会一直把队列弹空，因为每次只能从队首弹，想弹出队尾，只能把队列弹空
    q.push(x);
}

1.例题 求区间所有后缀最大值的位置

题目入口
该题是模板，今后注意到像“区间极值”一类的问题，可以考虑到单调队列。
该题 AC 代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long//扶苏的题通常（假的）都会卡ull
deque<int>q;
int n,k,a[1000010];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];//输入
        if(i>k && q.front()==i-k) q.pop_front();//过期删除，也叫延迟删除
        while(!q.empty() && a[i]>=a[q.back()]) q.pop_back();
        q.push_back(i);//模板操作
        if(i>=k)cout<<q.size()<<"\n";//输出
    }
    return 0;
}

此处细心的读者可能已经发现我单调队列用的 STL 是 deque，不是 queue，那么我就借此篇讲讲 deque（双端队列）。

deque 浅讲

其他例题

P1638 P1886 P2952 P8661 P7795

注：由于笔者的失误，没有控制好单调栈和单调队列的图的像素大小相同，以至于您的阅读不便，至此道歉！