栈与单调栈（Stack & Monotonic Stack）

作者： 作者的头像   huolong , 时间：2026-08-21 11:49:30 , 所有人可见, 阅读  50

栈与单调栈（Stack & Monotonic Stack）

一、 栈（Stack）的基本概念

1.1 定义与特性：后进先出 (LIFO)

栈是一种遵循后进先出（Last-In, First-Out，简称 LIFO）原则的线性数据结构。

这个概念可以用一个经典的生活实例来理解：一叠盘子。 * 放盘子 (Push)：你洗好一个新盘子，自然会把它放在最上面。 * 取盘子 (Pop)：当你要用盘子时，也总是从最上面拿走一个。

最后放上去的盘子，最先被拿走。这就是“后进先出”的核心思想。 在栈结构中，允许插入和删除的一端被称为栈顶 (Top)，另一端则是栈底 (Bottom)。所有操作都必须在栈顶进行，不允许直接访问栈底或栈中部的元素。

       Top ──> [ 30 ]  <-- 刚压入的元素（最先被弹出）
               [ 20 ]
    Bottom ──> [ 10 ]  <-- 最早压入的元素（最后被弹出）

1.2 核心操作

栈的基本操作非常简洁： * push(x)：将元素 $x$ 压入栈顶。 * pop()：移除/弹出栈顶元素。 * top()：查询栈顶元素的值，但不移除它。 * empty()：判断栈是否为空。 * size()：返回栈中当前有效元素的数量。

1.3 C++ 标准库实现：std::stack

在 C++ 中，标准模板库（STL）提供了现成的 std::stack。它是一个容器适配器（默认基于 std::deque 封装），屏蔽了双端操作，只暴露出符合 LIFO 原则的单端接口。

⚠️ WARNING（安全防护） 对一个空栈执行 top() 或 pop() 操作在标准中是未定义行为（Undefined Behavior, UB），在实际运行中通常会导致程序崩溃。在调用这类操作前，务必先通过 !s.empty() 进行安全检查。

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    stack<int> s; // 声明一个存放 int 类型元素的栈

    cout << "栈是否为空? " << (s.empty() ? "是" : "否") << "\n"; // 输出: 是

    s.push(10); // 压入 10, 栈状态（底->顶）: [10]
    s.push(20); // 压入 20, 栈状态（底->顶）: [10, 20]
    s.push(30); // 压入 30, 栈状态（底->顶）: [10, 20, 30]

    cout << "栈内元素数量: " << s.size() << "\n"; // 输出: 3
    cout << "当前栈顶元素: " << s.top() << "\n";  // 输出: 30

    s.pop(); // 弹出 30, 栈状态: [10, 20]
    cout << "弹出后栈顶元素: " << s.top() << "\n"; // 输出: 20

    s.pop(); // 弹出 20, 栈状态: [10]
    s.pop(); // 弹出 10, 栈状态: [] (空栈)

    cout << "此时栈是否为空? " << (s.empty() ? "是" : "否") << "\n"; // 输出: 是

    // 安全防御示范
    if (!s.empty()) {
        s.pop(); 
    }

    return 0;
}
  • 时空复杂度：栈的所有基本操作（push, pop, top, empty, size）的时间复杂度均为 $O(1)$。空间复杂度为 $O(N)$（$N$ 为栈中实际元素的数量）。

1.4 栈的典型应用

栈的 LIFO 特性使其在处理具有“对称性”、“嵌套性”或“回溯/撤销性”的问题时格外高效。

1.4.1 状态模拟：预测输出

  • 问题：分析以下代码片段，写出其最终输出结果。
#include <iostream>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    stack<int> s;
    for (int i = 1; i <= 5; ++i) {
        s.push(i);
    }
    int a = s.top(); s.pop();
    s.push(a - 2);
    s.push(s.top() + 1);
    cout << s.top() << " ";
    s.pop();
    cout << s.top() << "\n";
    return 0;
}
  • 手算模拟追踪过程：
  • for 循环：依次压入 $1, 2, 3, 4, 5$。栈状态（底 $\to$ 顶）：$[1, 2, 3, 4, 5]$。
  • int a = s.top(); s.pop();：$s.top()$ 为 $5$，因此变量 $a$ 赋值为 $5$。移除 $5$。栈状态：$[1, 2, 3, 4]$。
  • s.push(a - 2);：压入 $a - 2 = 3$。栈状态：$[1, 2, 3, 4, 3]$。
  • s.push(s.top() + 1);：此时栈顶为 $3$，压入 $3 + 1 = 4$。栈状态：$[1, 2, 3, 4, 3, 4]$。
  • cout << s.top() << " ";：输出当前的栈顶元素 4。
  • s.pop();：弹出栈顶的 $4$。栈状态：$[1, 2, 3, 4, 3]$。
  • cout << s.top() << "\n";：输出此时的栈顶元素 3。
  • 最终输出结果： text 4 3

1.4.2 括号匹配（Bracket Matching）

  • 题意概括： 给定一个只包含 (, ), {, }, [ 和 ] 的字符串，判断该括号字符串是否合法有效。 有效需满足：左括号必须用相同类型的右括号闭合，且必须以正确的顺序闭合（不可发生交叉嵌套）。

  • 核心分析： 括号的嵌套天然符合后进先出原则。 遇到左括号时，代表进入了更深一层的括号范围，我们将左括号执行压栈； 遇到右括号时，其必须与当前最内层（即最近压入、处于栈顶）的左括号类型完全匹配。

  • 非法情况判定：
    1. 遇到右括号时，栈已空（右括号多余，无左括号匹配）。
    2. 遇到右括号时，其类型与栈顶的左括号不匹配（交叉嵌套错误）。
    3. 遍历完字符串后，栈内仍残留有左括号（左括号多余，未闭合）。
#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isValid(string t) {
    stack<char> s;
    for (char c : t) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c); // 左括号压栈
        } else {
            if (s.empty()) return false; // 1. 右括号多余，匹配失败
            char top = s.top();
            s.pop();
            // 2. 类型不匹配校验
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return s.empty(); // 3. 检查是否有未闭合的左括号残留
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s1 = "()[]{}";
    string s2 = "([)]";
    cout << s1 << ": " << (isValid(s1) ? "Valid" : "Invalid") << "\n"; // Valid
    cout << s2 << ": " << (isValid(s2) ? "Valid" : "Invalid") << "\n"; // Invalid
    return 0;
}
  • 时空复杂度：单次遍历字符串，时间复杂度为 $O(L)$（$L$ 为字符串长度）；最坏情况下（如全为左括号）需要将元素全部压入，空间复杂度为 $O(L)$。

1.4.3 后缀表达式求值（RPN Evaluation）

  • 题意概括： 计算一个后缀表达式（逆波兰表达式，Reverse Polish Notation）的值。 例如输入："4 5 + 3 *"，对应常规的中缀表达式为：(4 + 5) * 3。

  • 算法逻辑： 从左向右扫描表达式：

  • 若遇到数字：将其压入栈。
  • 若遇到运算符：从栈顶弹出两个数字（先弹出的作为右操作数 $b$，后弹出的作为左操作数 $a$）进行对应运算，并将运算结果重新压入栈顶。
  • 扫描结束后，栈中唯一残留的数字即为最终计算结果。
#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

// 假设输入已按空格切分为字符串数组
int evalRPN(vector<string>& v) {
    stack<int> s;
    for (const string& t : v) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = s.top(); s.pop(); // 右操作数
            int a = s.top(); s.pop(); // 左操作数
            if (t == "+") s.push(a + b);
            else if (t == "-") s.push(a - b);
            else if (t == "*") s.push(a * b);
            else s.push(a / b);
        } else {
            s.push(stoi(t)); // stoi 将数字字符串转换为整型后压栈
        }
    }
    return s.top();
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<string> v = {"4", "13", "5", "/", "+"}; // 对应 (4 + (13 / 5))
    cout << "Result: " << evalRPN(v) << "\n"; // 输出: 6
    return 0;
}
  • 复杂度分析：每个数字和运算符仅被扫描处理一次，时间复杂度为 $O(N)$（$N$ 为表达式项数），空间复杂度为 $O(N)$。

二、 单调栈 (Monotonic Stack)

2.1 定义与核心特性

单调栈是一种特殊的栈，它在运行期间强制维持栈内元素从栈底到栈顶呈严格的单调递增（或单调递减）状态。

  • 工作机制： 在向栈中压入一个新元素 $x$ 时，不能无视条件直接执行 push，而是需要将 $x$ 与当前的栈顶元素进行比较：
  • 单调递增栈（栈底 $\to$ 栈顶递增）：若 $x$ 小于栈顶元素，为了维持栈的单调递增性质，我们必须不断弹出（pop）当前的栈顶元素，直到栈为空或栈顶元素小于或等于 $x$。此时再将 $x$ 压入栈。
  • 单调递减栈（栈底 $\to$ 栈顶递减）：若 $x$ 大于栈顶元素，为了维持递减性质，必须不断弹出栈顶元素，直到栈为空或栈顶元素大于或等于 $x$。此时再将 $x$ 压入栈。

💡 核心精髓： 这个不断“清理并驱逐”栈顶元素的过程是单调栈的核心所在。 当一个元素被 $x$ 强行弹出时，意味着新压入的元素 $x$ 是它在对应扫描方向上遇到的“第一个比它更小（或更大）”的元素。这使得单调栈成为了解决“寻找区间中下一个/上一个更大/更小元素”的 $O(N)$ 级利器。

2.2 典型应用：下一个更大元素 (Next Greater Element)

  • 题意概括： 给定一个数组 $v$，求数组中每个元素右侧第一个比它大的元素。若右侧没有更大的元素，对应结果记为 $-1$。 例如输入：[2, 1, 2, 4, 3]，输出：[4, 2, 4, -1, -1]。

  • 算法逻辑： 我们从左向右遍历数组，并使用单调递减栈来维护元素的下标：

  • 当前遍历到的元素为 $v[i]$。
  • 若栈不为空，且当前元素 $v[i]$ 严格大于栈顶下标对应的元素 $v[s.top()]$，说明 $v[i]$ 就是 $v[s.top()]$ 向右遇到的第一个更大元素。我们记录下结果 ans[s.top()] = v[i]，并弹出该栈顶下标。
  • 重复第 2 步，直到栈为空或 $v[i] \le v[s.top()]$。
  • 将当前下标 $i$ 压入栈（因为所有比它小的历史下标都已经被弹走，单调性得以完好维护）。
  • 遍历结束后，栈内残留的下标说明其右侧没有更大的数，我们将其对应的答案统一设为 $-1$。

C++ 代码实现

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// 返回每个元素右侧第一个比它大的数
vector<int> nextGreaterElement(const vector<int>& v) {
    int n = v.size();
    vector<int> ans(n);
    stack<int> s; // 单调递减栈，存放数组的索引下标

    for (int i = 0; i < n; ++i) {
        // 当栈顶元素小于当前元素时，说明找到了栈顶元素的右侧首个更大值
        while (!s.empty() && v[i] > v[s.top()]) {
            ans[s.top()] = v[i];
            s.pop();
        }
        s.push(i); // 将当前索引压栈
    }

    // 栈中残留的索引代表其右侧无更大元素，统一设为 -1
    while (!s.empty()) {
        ans[s.top()] = -1;
        s.pop();
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> v = {2, 1, 2, 4, 3};
    vector<int> res = nextGreaterElement(v);
    for (int x : res) {
        cout << x << " ";
    }
    cout << "\n"; // 输出: 4 2 4 -1 -1 
    return 0;
}
  • 时空复杂度分析： 虽然代码中出现了 while 嵌套在 for 循环中，但数组中的每一个下标最多只会执行一次入栈和一次出栈。因此，总时间复杂度为 $O(N)$（$N$ 为数组长度），空间复杂度为 $O(N)$（用于维护单调栈和结果数组）。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com