单调栈、单调队列课堂笔记

AAA光碟批发白蛇

2026-08-29 15:49:37

发布于：上海

2阅读

0回复

0点赞

课堂笔记

单调栈

使用场景：求每个ai右边第一个比它大的数字，在O(n)内解决这个问题。
核心思想：及时淘汰“永远不可能成为答案”的元素。
朴素做法：每个i都要向右扫描一次。若“i < j”且 “ai < aj”，那么当我们向右边寻找时，ai永远不会先于aj被选中——任何比ai大的数字如果在j右边，那么ai就应该在aj出现后淘汰。

实现方法：维护一个栈，站内元素从栈底到栈顶递减。
1、新元素ai到来时，所有比他小的元素，都等来了自己的答案，在弹栈的过程中记录答案。
2、ai入栈。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
int n , a[N] , ans[N];//ans[i] = 右边第一个比a[i]大的数的下标
stack<int> st;//栈里存下标，对应的值是从栈底到栈顶递减
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        while(st.size() && a[st.top()] < a[i]){
            ans[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    for(int i = 1; i <= n; i++){
        cout << ans[i] << ' ';
    }
    return 0;
}

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