单调栈、单调队列

shizhile0414

2026-08-29 15:50:23

发布于：上海

4阅读

0回复

0点赞

单调栈、单调队列

单调栈

使用场景：

求每个 $a_i$ 右边/左边第一个大于/小于其的数字，在 $O(n)$ 内解决这个问题。

核心思想：

及时淘汰"永远不会成为答案的元素"

朴素做法：每个 $i$ 都要向右扫描一次。若 $i<j$ 且 $a_i<a_j$ ，那么当我们向右寻找时， $a_i$ 永远不会先于 $a_j$ 被选中——任何比 $a_i$ 大的数学如果在 $j$ 右边， $a_j$ 都会先拦住它，那么 $a_i$ 就应该在 $a_j$ 出现后淘汰。

实现方法：

维护一个栈，栈内元素从栈底到栈顶递减。

1.新元素 $a_i$ 到来时，所有比它小的元素，都等来了自己的答案，在弹栈的过程中记录答案。

2.之后， $a_i$ 入栈

代码：

int a[N],ans[N],n;\\ans用于存储最终答案
stack<int> st;\\单调栈
for(int i=1;i<=n;i++){
    while(!st.empty()&&a[st.top()]<a[i]){ \\持续弹出
        ans[st.top()]=i;
        st.pop();
    }
    st.push(i);
}

总结：

栈的单调性（栈底到栈顶）	适用场景	触发弹出时的逻辑
单调递减（大->小）	寻找每个元素左侧/右侧第一个更大的元素	当新元素>栈顶新元素是栈顶的第一个更大值。
单调递减（小->大）	寻找每个元素左侧/右侧第一个更小的元素	当新元素<栈顶新元素是栈顶的第一个更小值。

单调队列（双指针）

使用场景：

求每个长为 $k$ 的窗口内的最大值。

同样看浪费的部分：若 $i<j$ 且 $a_i\le a_j$ ，只要 $a_j$ 在窗口内， $a_i$ 就永远不可能是最大值，窗口保留 $a_j$ ，且 $a_i$ 可以立刻淘汰。

维护一个双端队列，存下标，对应值从队头到队尾递减：

· 队尾：新元素到来时，把队尾所有不大于它的元素弹掉，再把新元素接在队尾；

· 队头：检查队头下标是否已经滑出窗口，是则弹出；

· 答案：队头即当前最大值。

代码

int n,a[N];
deque<int> q;
//求区间最小值
for(int i=1;i<=n;i++){
    while(!q.empty()&&a[q.back()]>=a[i]){
        q.pop_back();
    }
    q.push_back(i);
    while(q.front()<=i-k){
        q.pop_front();
    }
    if(i>=k){
        cout<<a[q.front()]<<" ";//输出
    }
}
//区间最大值
for(int i=1;i<=n;i++){
    while(!q.empty()&&a[q.back()]<=a[i]){
        q.pop_back();
    }
    q.push_back(i);
    while(q.front()<=i-k){
        q.pop_front();
    }
    if(i>=k){
        cout<<a[q.front()]<<" ";//输出
    }
}