单调栈和单调队列

算法分析

数据结构	时间复杂度	空间复杂度	典型用途
单调栈	$O(n)$	$O(n)$	找下一个更大 / 更小元素
单调队列	$O(n)$	$O(n)$	滑动窗口最大 / 最小值

单调栈

单调栈是一种在栈内部维持元素单调性的技巧，常用于求“每个元素的下一个更大/更小元素”等问题。
单调栈即要求栈内元素具有单调性（单调递增/单调递减/单调不增/单调不降），并且同时优先保留后加入的元素。

思路

使用一个栈 sta，栈中存储的是“候选元素”的下标（下同）。
栈内元素按值单调递增（或递减）。以“找下一个更大元素”为例，栈内维护单调递增。
遍历数组 A：
1. 当 A[i] 大于栈顶元素 A[sta.top()] 时，说明栈顶元素找到了它的下一个更大值，弹出栈顶并记录答案。
2. 重复上述步骤直到栈空或 A[i] <= A[sta.top()]。
3. 将当前下标 i 入栈。
最后栈中剩余元素没有下一个更大值，可统一置为 -1 或其他默认值。

代码示例

例题：Luogu P5788 - 【模板】单调栈

#include<bits/stdc++.h>
using namespace std;
const int LEN=3e6+5;
int a[LEN],f[LEN];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)  cin>>a[i];
    stack<int> sta;//存储下标
    for(int i=1;i<=n;i++)
    {
        //找到一个更大的元素下标
        while(!sta.empty()&&a[i]>a[sta.top()])
        {
            f[sta.top()]=i;
            sta.pop();//维护单调性
        }
        sta.push(i);
    }
    for(int i=1;i<=n;i++)  cout<<f[i]<<' ';
    return 0;
}

单调队列

单调队列通常用来维护滑动窗口中的最大值或最小值，以 O(1) 均摊复杂度取窗口值。常见场景是“滑动窗口最大值”和“滑动窗口最小值”。

思路

使用 deque<int> dq，存储窗口内的下标，并保持队列内对应的值单调递减（以求最大值为例）。
遍历数组 A，下标为 i：
1. 如果队头 dq.front() 已经滑出窗口范围（i - dq.front() >= k），则 dq.pop_front()。
2. 将当前元素与队尾元素比较，若 A[i] 大于等于 A[dq.back()]，弹出队尾，直到队尾大于当前元素。
3. 将 i 推入队尾。
4. 当窗口形成（i >= k-1）时，队头即为窗口最大值下标，记录 A[dq.front()]。

代码示例

例题：Luogu P1886 - 滑动窗口 /【模板】单调队列

#include<bits/stdc++.h>
using namespace std;
const int LEN=1e6+5;
int a[LEN],n,k;
//单调递增队列求最小值
void getMin()
{
    deque<int> dq;
    for(int i=1;i<=n;i++)
    {
        //队头元素是否滑出窗口
        if(!dq.empty()&&dq.front()<=i-k)  dq.pop_front();

        //维护递增性：弹出比当前值大的队尾元素
        while(!dq.empty()&&a[dq.back()]>a[i])  dq.pop_back();

        dq.push_back(i);

        //输出窗口最小值
        if(i>=k)  cout<<a[dq.front()]<<' ';
    }
}
//单调递减队列求最大值
void getMax()
{
    deque<int> dq;
    for(int i=1;i<=n;i++)
    {
        //队头元素是否滑出窗口
        if(!dq.empty()&&dq.front()<=i-k)  dq.pop_front();

        //维护递减性：弹出比当前值小的队尾元素
        while(!dq.empty()&&a[dq.back()]<a[i])  dq.pop_back();

        dq.push_back(i);

        if(i>=k)  cout<<a[dq.front()]<<' ';
    }
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)  cin>>a[i];
    getMin();//输出每个窗口的最小值
    cout<<endl;
    getMax();//输出每个窗口的最大值
    return 0;
}

小结

单调栈解决“下一个更大/更小元素”、直方图最大矩形等问题。
单调队列主要用于“滑动窗口”相关最大/最小值。
维护方式：逐个元素进来时，先弹出不符合单调原则的元素，再将当前下标压入；必要时再弹出过期元素。