InoueMoby's Blog

前言

想象你在用浏览器上网。你点开了一个链接,又点开了一个,又一个。现在你按”返回”—浏览器会把你带去最近访问的页面,而不是最早访问的。因为”历史记录”是按照后进先出的方式管理的:最后放进来的,最先被取出来。

这就是栈(Stack)。函数调用栈、括号匹配、撤销操作—到处都是它的身影。

队列(Queue)则是相反的逻辑—排在队伍最前面的人最先被服务,先进先出。BFS 用队列逐层展开搜索,操作系统用队列调度任务。

但本篇真正的重头戏是第三位主角—单调栈。它能在 $O(n)$ 时间内解决”每个元素左/右边第一个比它大/小的元素”这类问题,代码只有几行,威力却极大。

问题的本质

栈:为什么”后进先出”这么有用?

先忘掉数据结构,想一个生活场景:桌上有一摞盘子。你每次只能拿最上面的那个,也只能往最上面放新的。这就叫 LIFO(Last In, First Out)。

为什么这个限制反而在算法里有用?因为很多问题的答案藏在最近的历史里。比如括号匹配—一个 ) 必须和离它最近的还没有被匹配的 ( 配对。你不需要看所有的 (,只需要看最近的那一个。栈完美地维护了”最近未匹配”这个信息。

单调栈:用”淘汰赛”的思路找邻居

考虑这个问题:对数组中每个元素,找到它右边第一个比它大的元素。

朴素做法是 $O(n^2)$ —对每个元素往右扫。但想象一场淘汰赛:新选手 $a_i$ 来了,它淘汰掉所有比它弱的( $\le a_i$ 的)旧选手,因为那些弱者以后再也不可能成为任何人的”右边第一个更大”了— $a_i$ 比它们更新、更大、位置更近。

被淘汰的选手永远离开,剩下的选手从底到顶递减排列。这就是”单调栈”—栈里元素始终保持单调性。每个元素最多进出栈各一次,总时间 $O(n)$ 。

理论 + 代码

栈的基本操作

C++ STL 提供了 stack,支持两种核心操作:

#include <stack>
using namespace std;

stack<int> st;
st.push(x);       // 1 压入元素到栈顶
st.pop();         // 2 弹出栈顶元素(不返回值)
int t = st.top(); // 3 查看栈顶元素
bool e = st.empty(); // 4 判空
int s = st.size();   // 5 元素个数

经典应用—括号匹配:遇到左括号就压栈,遇到右括号就检查栈顶是否是对应的左括号。

bool valid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{')  // 1 左括号入栈
            st.push(c);
        else {
            if (st.empty()) return false;       // 2 没有可匹配的左括号
            char t = st.top(); st.pop();        // 3 弹出最近的左括号
            if (c == ')' && t != '(') return false;
            if (c == ']' && t != '[') return false;
            if (c == '}' && t != '{') return false;
        }
    }
    return st.empty();  // 4 最后栈必须为空
}

为什么栈是对的数据结构? 因为括号配对遵循”最近优先”原则—一个右括号总是和离它最近的未匹配左括号配对。栈的 LIFO 特性天然地维护了”最近”这个信息。

队列的基本操作

队列是 FIFO(First In, First Out)—先到先服务:

#include <queue>
using namespace std;

queue<int> q;
q.push(x);       // 1 入队(尾部)
q.pop();         // 2 出队(头部)
int f = q.front(); // 3 查看队头
int b = q.back();  // 4 查看队尾

队列的核心应用是 BFS(广度优先搜索)。在图论篇中我们会详细介绍,这里只需记住:凡是需要”按层”或”按距离”处理的问题,就用队列。

单调栈

核心模板

问题:对数组中每个元素,求它右边第一个比它大的元素的位置。

vector<int> next_greater(vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);   // 1 默认 -1 表示不存在
    stack<int> st;             // 2 栈存下标,不存值
    for (int i = 0; i < n; i++) {
        // 3 新元素 a[i] 比栈顶大 → 栈顶找到了答案
        while (!st.empty() && a[st.top()] < a[i]) {
            ans[st.top()] = i;  // 4 a[i] 是 a[st.top()] 右边第一个比它大的
            st.pop();
        }
        st.push(i);  // 5 当前下标入栈,等待未来的元素来"解答"它
    }
    return ans;
}

为什么是对的? 关键理解三点:

栈内元素递减:每次入栈前,比当前元素小的都被弹出了,所以栈底到栈顶始终递减。
弹出 = 找到答案:a[i] 比 a[st.top()] 大,且 i 在 st.top() 右边。中间不可能有其他元素比 a[st.top()] 大—否则 st.top() 早就被弹出了。
每个元素最多进出栈各一次:所以总时间是 $O(n)$ 。

四种变体速查

问题	扫描方向	栈的单调性	比较方式
右边第一个更大	左→右	递减栈	`a[st.top()] < a[i]`
右边第一个更小	左→右	递增栈	`a[st.top()] > a[i]`
左边第一个更大	右→左	递减栈	`a[st.top()] < a[i]`
左边第一个更小	右→左	递增栈	`a[st.top()] > a[i]`

记忆口诀:求”更大”用递减栈(小的被弹走,大的留下);求”更小”用递增栈。

模拟走一遍

以 $a = [3, 1, 4, 2, 5]$ 求”右边第一个更大”为例:

步骤	当前元素	弹出	栈(存下标)	ans
i=0	a[0]=3	无	[0]	[-1,-1,-1,-1,-1]
i=1	a[1]=1	无	[0,1]	[-1,-1,-1,-1,-1]
i=2	a[2]=4	弹出1,0	[2]	[2,2,-1,-1,-1]
i=3	a[3]=2	无	[2,3]	[2,2,-1,-1,-1]
i=4	a[4]=5	弹出3,2	[4]	[2,2,4,4,-1]

最终 ans = [2, 2, 4, 4, -1],即:

a[0]=3 右边第一个更大在位置 2(值为 4)✓
a[1]=1 右边第一个更大在位置 2(值为 4)✓
a[2]=4 右边第一个更大在位置 4(值为 5)✓
a[3]=2 右边第一个更大在位置 4(值为 5)✓
a[4]=5 右边没有更大的,-1 ✓

例题

例题 1:TB A60 - Stock Price

题目:给定 $N$ 天的股价 $A_1, A_2, \ldots, A_N$ (互不相同)。对每一天 $d$ ,求最大的 $i < d$ 使得 $A_i > A_d$ (即”起算日”—左边第一个比它高的股价出现在第几天)。如果不存在,输出 $-1$ 。

数据范围: $1 \le N \le 2 \times 10^5$

— AtCoder Tessoku Book A60

分析:这就是”左边第一个更大”问题。从左到右扫描,维护递减栈。

代码:

#include <cstdio>
#include <stack>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    stack<pair<int,int>> st;  // 1 (股价, 日期编号)
    for (int i = 1; i <= N; i++) {
        int p;
        scanf("%d", &p);
        // 2 弹出所有 <= p 的,它们不可能是后续任何人的答案
        while (!st.empty() && st.top().first <= p) st.pop();
        // 3 栈顶就是左边第一个比 p 大的
        printf("%d%c", st.empty() ? -1 : st.top().second, " \n"[i == N]);
        st.push({p, i});  // 4 当前元素入栈
    }
    return 0;
}

逐行解析:

1 栈存 (股价, 日期编号) 对。之所以要存日期编号,是因为弹出后我们需要知道答案的日期。
2 核心循环:维护单调递减。新来的 $p$ 淘汰所有 $\le p$ 的旧元素—它们比 $p$ 弱、比 $p$ 旧、比 $p$ 远,永远不可能成为后续任何人的”左边第一个更大”。
3 弹完后,栈顶(如果存在)就是左边第一个比 $p$ 大的。如果栈空,说明左边没有比它大的,输出 $-1$ 。
4 每个元素最多进出栈各一次,总时间 $O(N)$ 。

验证: $A = [6, 2, 5, 3, 1, 4]$ ,输出 $-1, 1, 1, 3, 4, 3$ 。✓

例题 2:TB B51 - Bracket

题目:给定一个合法的括号序列 $S$ 。输出每对配对括号的位置(1-indexed),按 $\max(l, r)$ 升序排列。

数据范围: $1 \le |S| \le 2 \times 10^5$

— AtCoder Tessoku Book B51

分析:这道题不需要单调栈,只需要最基础的栈配对括号。遇到 ( 压入位置,遇到 ) 弹出栈顶—栈顶的 ( 与当前 ) 配对。

代码:

#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;

pair<int,int> ans[200010];
int cnt = 0;

int main() {
    char S[200010];
    scanf("%s", S);
    int n = 0;
    while (S[n]) n++;

    stack<int> st;  // 1 存左括号的下标
    for (int i = 0; i < n; i++) {
        if (S[i] == '(') {
            st.push(i);  // 2 遇到 ( 入栈
        } else {
            int j = st.top(); st.pop();  // 3 遇到 ) 弹出配对的 (
            ans[cnt++] = {j + 1, i + 1}; // 4 转为 1-indexed 记录配对
        }
    }

    // 5 栈的 LIFO 特性使内层括号先被发现,需要排序
    sort(ans, ans + cnt, [](auto& a, auto& b) {
        return max(a.first, a.second) < max(b.first, b.second);
    });
    for (int i = 0; i < cnt; i++)
        printf("%d %d\n", ans[i].first, ans[i].second);
    return 0;
}

逐行解析:

1 栈只存 ( 的下标位置。
23 这是栈配对括号的核心逻辑:( 入栈等待,) 来了就弹出最近的 ( 与它配对。因为括号序列合法,所以栈一定不空。
4 为什么要转 1-indexed?因为 AtCoder 通常用 1-indexed。
5 由于栈的 LIFO 特性,嵌套最深的括号最先被配对。题目要求按 $\max(l, r)$ 升序输出,所以需要排序。 $O(n \log n)$ 。

验证:(())() → 配对 (2,3), (1,4), (5,6),排序后输出正确。✓

例题 3:M&A 086 - Parentheses Check

题目:给定长度为 $N$ 的、由 ( 和 ) 组成的字符串 $S$ ,判断它是否是合法的括号序列。

数据范围: $1 \le N \le 5 \times 10^5$

— AtCoder M&A 086

分析:这是例题 2 的简化版—不需要找配对关系,只需判断合法性。因为只有一种括号,不需要真的用栈存内容,只需要维护一个计数器—未匹配的 ( 的个数。

代码:

#include <cstdio>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);        // 1 先读长度
    char S[500010];
    scanf("%s", S);
    int depth = 0;          // 2 当前"深度"= 未匹配的 ( 的个数
    for (int i = 0; i < N; i++) {
        if (S[i] == '(')
            depth++;        // 3 遇到 ( 深度 +1
        else {
            depth--;        // 4 遇到 ) 深度 -1
            if (depth < 0) { // 5 深度为负 → ) 比 ( 多,非法
                printf("No\n");
                return 0;
            }
        }
    }
    printf("%s\n", depth == 0 ? "Yes" : "No"); // 6 最后深度必须为 0
    return 0;
}

逐行解析:

1 题目先给 $N$ 再给 $S$ ,所以先读 $N$ 。
2 用 depth 代替栈。因为括号只有一种类型,栈里全是 (,只需要知道数量。
5 如果 depth 变成负数,说明出现了多余的 ),立刻判定非法。
6 扫描结束后,depth 必须为 0(所有 ( 都被匹配了),否则有多余的 (。

例题 4:T90 061 - Deck(★2)

题目:最初牌堆为空,执行 $Q$ 次操作。操作有三种:

$t_i=1$ :把写着 $x_i$ 的牌放到牌堆最上面

$t_i=2$ :把写着 $x_i$ 的牌放到牌堆最下面

$t_i=3$ :查询牌堆从顶数第 $x_i$ 张牌上写的数

数据范围: $2 \le Q \le 10^5$

— AtCoder Typical 90 061

分析:操作 1 和 2 是双端队列的基本操作(push_front 和 push_back)。操作 3 要求查询第 $k$ 个元素—deque 支持随机访问 dq[k],直接用即可。

代码:

#include <cstdio>
#include <deque>
using namespace std;

int main() {
    int Q;
    scanf("%d", &Q);
    deque<int> dq;
    while (Q--) {
        int t, x;
        scanf("%d%d", &t, &x);
        if (t == 1)
            dq.push_front(x);  // 1 放到最上面
        else if (t == 2)
            dq.push_back(x);   // 2 放到最下面
        else
            printf("%d\n", dq[x - 1]); // 3 查询第 x 张(0-indexed 所以 -1)
    }
    return 0;
}

逐行解析:

1 push_front:把新牌放到牌堆最上面。
2 push_back:把新牌放到牌堆最下面。
3 dq[x-1]:deque 支持下标访问,第 $x$ 张在 0-indexed 中是 x-1。

验证:样例 1,操作序列 1 2, 1 1, 2 3 后牌堆从顶到底为 [1,2,3],查询第 1/2/3 张分别输出 1/2/3。✓

例题 5：T90 006 — Smallest Subsequence（★5）

题目：给定长度为 $N$ 的由小写字母组成的字符串 $S$ 和整数 $K$ 。从 $S$ 中选取 $K$ 个字符（保持原始顺序，即子序列），使得组成的字符串字典序最小。

数据范围： $1 \le K \le N \le 10^5$

—— AtCoder Typical 90 006

分析：这道题是单调栈的升级应用——字典序最小子序列。

核心思路：用单调递增栈。从左到右扫描 $S$ ，对每个字符 $S[i]$ ：

当栈顶字符 $> S[i]$ ，且”剩余可用的字符”足够（即 $i$ 后面还有足够的字符来凑满 $K$ 个），就弹出栈顶（选 $S[i]$ 更优）。
把 $S[i]$ 压入栈。
最终栈中的前 $K$ 个字符就是答案。

关键条件：弹出栈顶的条件是”栈的大小 $- 1 +$ 剩余字符数 $\ge K$ “，即弹出后仍然能凑够 $K$ 个。

代码：

#include <cstdio>
#include <stack>
#include <string>
using namespace std;

int main() {
    int N, K;
    char S[100010];
    scanf("%d%d", &N, &K);  // ① 先读 N 和 K
    scanf("%s", S);

    stack<char> st;
    for (int i = 0; i < N; i++) {
        // ② 弹出比 S[i] 大的栈顶，前提是弹完后还能凑够 K 个
        while (!st.empty() && st.top() > S[i]
               && (int)st.size() - 1 + (N - i) >= K) {
            st.pop();
        }
        // ③ 栈的大小还没到 K 就压入
        if ((int)st.size() < K)
            st.push(S[i]);
    }
    // ④ 从栈底到栈顶就是答案
    string ans;
    while (!st.empty()) {
        ans += st.top();
        st.pop();
    }
    for (int i = ans.size() - 1; i >= 0; i--)
        printf("%c", ans[i]);
    printf("\n");
    return 0;
}

逐行解析：

① 输入格式：先 $N$ $K$ ，再字符串 $S$ 。
② 核心条件：st.top() > S[i]（选 $S[i]$ 更优）且 st.size() - 1 + (N - i) >= K（弹出后，栈里剩下的 + 还没扫描的 $\ge K$ ，凑得够）。
③ 只压入到栈大小 $< K$ 为止，保证最终恰好 $K$ 个字符。
④ 栈是从底到顶递增的，所以从栈顶到栈底就是答案的逆序。反转输出。

验证： $S=$ atcoder, $K=3$ 。栈的过程：a入→t入→c来弹t→c入→o入→d来弹o→d入→e入→r入。最终栈底到顶 a,c,d，输出 acd。✓

参考文献

教材讲解 — 競技プログラミングの鉄則第 8 章

基础练习 - アルゴリズムと数学演習問題集

086 Parentheses Check【例题】

系统练习 - 競技プログラミングの鉄則

实战练习 - 競プロ典型 90 問

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

栈、队列与单调栈

后进先出与先进先出的世界--单调栈的 O(n) 妙用

前言

问题的本质

栈:为什么”后进先出”这么有用?

单调栈:用”淘汰赛”的思路找邻居

理论 + 代码

栈的基本操作

队列的基本操作

单调栈

核心模板

四种变体速查

模拟走一遍

例题

例题 1:TB A60 - Stock Price

例题 2:TB B51 - Bracket

例题 3:M&A 086 - Parentheses Check

例题 4:T90 061 - Deck(★2)

例题 5：T90 006 — Smallest Subsequence（★5）

参考文献

系列索引

栈、队列与单调栈