ZaynPei Lv6
  2025-11-07 20:41:52 2025-11-07 20:41:52 Created   2025-11-12 19:44:03 2025-11-12 19:44:03 Updated  3.8k Words  15 Mins

栈

栈是一种后进先出（LIFO）的数据结构，支持基本操作：入栈（push）、出栈（pop）和查看栈顶元素（top）。栈的应用场景包括表达式求值、括号匹配、深度优先搜索等。

邻项消除 & 合法括号字符串

这两个是栈的最经典应用，因为它们的思想完全一致。

核心思想：

  • 遍历你的输入（如一个字符串）。
  • 使用一个栈来维护一个“尚未被消除/匹配”的元素序列。
  • 当你遇到一个新元素 current 时，你去看它和“栈顶”元素 stack.top()（即最近一个尚未被消除的元素）是否能“配对”。
    • 如果能配对：说明 current 和 stack.top() 互相消除了。你执行 stack.pop()，并且不将 current 入栈。
    • 如果不能配对：说明 current 暂时无法被消除，你将它 stack.push()，等待它未来的“配对者”出现
  • 遍历结束后，栈内剩下的元素就是“无法被消除/匹配”的元素。
    • 对于邻项消除问题，栈内剩下的元素就是最终结果。
    • 对于括号匹配问题，栈内剩下的元素数量就是无法被匹配的括号数量。

单调栈

单调栈是一种特殊的栈数据结构，它在入栈和出栈操作时保持栈内元素的单调性（从栈底到栈顶递增或递减）。其核心思想，是在 O(n) 的一次遍历中，为数组中的每一个元素，快速找到它左侧或右侧(取决于遍历方向)的第一个比它“大”（或“小”）的元素。

它是如何工作的？ 以“单调递增栈”（栈底到栈顶）为例，当一个新元素 x 准备入栈时：

  1. 比较：x 会和栈顶 st.top() 比较。
  2. “清洗”：
    • 如果 x < st.top()，说明栈顶元素 st.top() “没用了”。为什么？因为它比 x 大，而且比 x 旧（在 x 左侧）。如果将来有一个元素 y（在 x 右侧）在寻找它“左侧第一个更小的元素”，y 会先看到 x，而永远不会看到 st.top()。
    • 因此，我们弹出 (pop) st.top()，然后 x 继续和新的栈顶比较。
    • 这个过程会一直持续，直到 st.top() <= x。
  3. 入栈：x 入栈。

通过这个“清洗”过程，栈内始终维护了一个单调递增的序列，这个序列里的元素都是“有潜力”的（它们都还在等待右侧第一个比自己小的元素）。

单调栈目前主要有四大应用场景:

1. 基础：寻找下一个更大/更小元素 (NGE/NSE)

问题：为数组中每个 nums[i]，找到它右侧第一个比它大的元素 nums[j]（j > i, nums[j] > nums[i]）。 解法：使用一个单调递减的栈（栈内存放下标）。 - 遍历数组 i 从左到右。 - while (!st.empty() && nums[i] > nums[st.top()])： - 这说明，nums[i] 是 st.top() 所代表的那个元素的“右侧第一个更大元素”。 - 找到了！ans[st.top()] = nums[i] (或 j - i，根据题目要求)。 - st.pop()。 - st.push(i)：nums[i] 入栈，等待它“右侧第一个更大元素”的出现。

例如每日温度: 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果不存在更高温度，答案为 0 。(LC 739)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
```cpp
// 单调栈解法：每日温度
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> indexes;         // 栈中存储下标，维护一个单调递增栈（栈底到栈顶温度递增）
        vector<int> ans(n, 0);      // 初始化答案数组，默认 0

        for (int i = 0; i < n; i++) {
            int cur = temperatures[i];
            // 如果当前温度比栈顶下标对应的温度高，说明找到了“右侧第一个更高温度”
            while (!indexes.empty() && temperatures[indexes.top()] < cur) {
                int index = indexes.top();
                ans[index] = i - index; // 计算间隔天数
                indexes.pop();
            }
            indexes.push(i); // 当前下标入栈，等待未来更高温度
        }
        return ans;
    }
};

2. 进阶：柱状图中的最大矩形面积

这是单调栈最经典的应用。问题描述: 给定 n 个非负整数表示每个柱子的高度图，宽度均为 1，计算在该柱状图中，能够勾勒出来的矩形的最大面积(LC 84)。

解法：

  • 遍历每一个柱子 h[i]，并假设它就是矩形的最终高度。
  • 我们需要找到这个矩形能向左和向右延伸的最大宽度。
  • 向左：找到 h[i] 左侧第一个小于 h[i] 的柱子 h[l]。
  • 向右：找到 h[i] 右侧第一个小于 h[i] 的柱子 h[r]。
  • 这个 h[i] 的矩形面积就是 h[i] * (r - l - 1)。

这就是“寻找下一个更小元素”(NSE) 问题。你可以通过两次遍历（一次找左侧，一次找右侧）来解决。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
```cpp
// 柱状图中的最大矩形面积（单调栈解法）
// 目标：对于每个柱子 heights[i]，找到其左右第一个比它小的柱子，计算最大面积
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> left_s;           // 用于计算每个柱子左侧第一个更小元素的下标
        vector<int> left_vec(n, -1); // left_vec[i] 记录 heights[i] 左侧第一个更小元素的下标，默认为 -1
        stack<int> right_s;          // 用于计算每个柱子右侧第一个更小元素的下标
        vector<int> right_vec(n, n); // right_vec[i] 记录 heights[i] 右侧第一个更小元素的下标，默认为 n

        int max_area = 0;

        // 1. 计算每个柱子右侧第一个更小元素的下标
        for (int i = 0; i < n; i++) {
            int cur = heights[i];
            // 如果当前柱子比栈顶柱子小，说明当前柱子是栈顶柱子的右侧第一个更小元素
            while (!right_s.empty() && cur < heights[right_s.top()]) {
                right_vec[right_s.top()] = i;
                right_s.pop();
            }
            right_s.push(i);
        }

        // 2. 计算每个柱子左侧第一个更小元素的下标
        for (int i = n - 1; i >= 0; i--) {
            int cur = heights[i];
            // 如果当前柱子比栈顶柱子小，说明当前柱子是栈顶柱子的左侧第一个更小元素
            while (!left_s.empty() && cur < heights[left_s.top()]) {
                left_vec[left_s.top()] = i;
                left_s.pop();
            }
            left_s.push(i);
        }

        // 3. 计算每个柱子作为矩形高度时的最大面积
        for (int i = 0; i < n; i++) {
            int cur_area = heights[i] * (right_vec[i] - left_vec[i] - 1);
            max_area = max(max_area, cur_area);
        }
        return max_area;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#### 贡献法：子数组的最小值之和

这是单调栈最精妙的应用。问题描述: 给定一个整数数组 nums ，返回所有非空子数组的最小值之和。(由于答案可能很大，因此返回答案对 10^9 + 7 取余后的结果)(LC 907)

核心思想（贡献法）：我们不遍历子数组，我们**遍历每一个元素 nums[i]**。
- 我们问：nums[i] 作为最小值，在多少个子数组中出现过？
- 同样，我们需要找到 nums[i] 的左侧第一个更小元素 (下标 l) 和右侧第一个更小元素 (下标 r)。
- 这说明 nums[i] 是**开区间 (l, r) 内的唯一最小值**。任何一个起点在 `(l, i]` 之间（共 **i - l** 种选择）且终点在 `[i, r)` 之间（共 **r - i** 种选择）组成的子数组，其最小值都是 nums[i]。
- nums[i] 的总贡献 = nums[i] * (i - l) * (r - i)。
- 用单调栈求出所有 l 和 r，然后 $O(n)$ 累加总贡献。
```cpp
class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        
        // 1. 计算左边界 left[i]
        // left[i] = l, 其中 l 是 arr[i] 左侧第一个“严格小于” arr[i] 的元素下标
        // 我们使用一个单调递增栈
        std::vector<int> left(n);
        std::stack<int> st_left;
        for (int i = 0; i < n; ++i) {
            // 解释: 栈顶元素如果 >= 当前元素，说明它不是 arr[i] 的左边界
            // (我们在找严格小于的)
            // 并且它也不是它右侧任何元素的左边界了，弹出
            while (!st_left.empty() && arr[st_left.top()] >= arr[i]) {
                st_left.pop();
            }
            // 解释: 栈为空，说明左侧没有更小元素；否则，栈顶就是左边界
            left[i] = st_left.empty() ? -1 : st_left.top();
            st_left.push(i);
        }

        // 2. 计算右边界 right[i]
        // right[i] = r, 其中 r 是 arr[i] 右侧第一个“小于或等于” arr[i] 的元素下标
        // 我们也使用一个单调递增栈 (但从右往左遍历)
        std::vector<int> right(n);
        std::stack<int> st_right;
        for (int i = n - 1; i >= 0; --i) {
            // 解释: 栈顶元素如果 > 当前元素，说明它不是 arr[i] 的右边界
            // (我们在找小于或等于的)
            while (!st_right.empty() && arr[st_right.top()] > arr[i]) {   // 注意这里是严格大于, 因为要避免两个栈都是大于等于导致重复计算
                st_right.pop();
            }
            // 解释: 栈为空，说明右侧没有更小或相等元素；否则，栈顶就是右边界
            right[i] = st_right.empty() ? n : st_right.top();
            st_right.push(i);
        }

        // 3. 累加贡献
        long long total_sum = 0;
        int MOD = 1e9 + 7;

        for (int i = 0; i < n; ++i) {
            // 解释: l = left[i], r = right[i]
            // 左侧的起点选择数: i - l
            // (j 可以在 (l, i] 范围内, 即 l+1, l+2, ..., i)
            long long left_span = i - left[i];

            // 解释: 右侧的终点选择数: r - i
            // (k 可以在 [i, r) 范围内, 即 i, i+1, ..., r-1)
            long long right_span = right[i] - i;

            // 贡献 = arr[i] * (左侧选择数) * (右侧选择数)
            long long contribution = (arr[i] * left_span * right_span);
            
            total_sum = (total_sum + contribution) % MOD;
        }

        return (int)total_sum;
    }
};

最小字典序：移掉 K 位数字

这是单调栈结合贪心思想的应用。问题描述: 给你一个以字符串表示的非负整数 num ，移除这个数中的 k 位数字，使得剩下的数字最小。返回移除 k 位数字后得到的最小整数，以字符串形式表示。(LC 402)

核心思想：

  • 为了让数字尽可能小，我们希望高位（左侧）的数字尽可能小。
    • 因为高位数字权重更大，假如有两个数字 a 和 b，如果 a < b，那么把 a 放在高位比把 b 放在高位更能减小整体数值。
  • 我们使用一个单调递增的栈来维护我们“保留”的数字。
  • 遍历数字字符串，for (char c : num)：
    • while (!st.empty() && k > 0 && c < st.top())：
      • 解释：新来的 c 比栈顶元素（已保留的数字）更小，并且我们还有删除的名额 (k > 0)。
      • 贪心：我们应该“扔掉”栈顶那个更大的数字，换成 c。
      • st.pop(); k–;
    • st.push(c);
  • 最终，栈中就保留了最小的序列。

例题: 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈

这道题的关键在于: 如何在 O(1) 时间内获取当前栈中的最小值？这意味着我们不能仅仅保存一个最小值变量, 因为当我们弹出栈顶元素时, 这个最小值可能不再是栈中的最小值了.

一个思路是使用一个辅助栈来跟踪当前的最小值。每当我们推入一个新元素时, 我们将其与当前的最小值进行比较, 并将较小的那个值也推入辅助栈. 这样, 辅助栈的栈顶始终保存着当前栈中的最小值. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stack>
#include <climits>    // 用于 INT_MAX
class MinStack {
private:
    std::stack<int> stk;     // 主栈
    std::stack<int> min_stk; // 辅助栈，存储历史最小值

public:
    MinStack() {
        // 初始化辅助栈，放入一个“哨兵”值，简化 push 逻辑
        min_stk.push(INT_MAX); 
    }
    
    // O(1)
    void push(int val) {
        // 1. 主栈正常推入
        stk.push(val);
        
        // 2. 辅助栈推入当前最小值
        // 解释：val 与 min_stk 的栈顶 (即之前的最小值) 比较，
        // 将较小者推入，确保 min_stk 顶部永远是当前最小值。
        int current_min = std::min(val, min_stk.top());
        min_stk.push(current_min);
    }
    
    // O(1)
    void pop() {
        // 解释：两个栈必须同时弹出，以保持状态同步。
        if (!stk.empty()) {
            stk.pop();
            min_stk.pop();
        }
    }
    
    // O(1)
    int top() {
        return stk.top();
    }
    
    // O(1)
    int getMin() {
        // 解释：min_stk 的栈顶就是当前栈中所有元素的最小值。
        return min_stk.top();
    }
};
还有一种不占用额外空间的解法, 通过在栈中存储元素与当前最小值的差值来实现.

我们只使用一个栈 stk 和一个变量 min_ele。min_ele 变量始终保存栈中的当前最小值; stk 栈中不直接存储元素 val，而是存储 val 与入栈前的 min_ele 之间的差值 (diff)。 > 为了防止 val - min_ele 溢出 int（例如 val=INT_MAX, min_ele=INT_MIN），我们必须使用 long long 来存储差值和 min_ele。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stack>
#include <climits> // 用于 INT_MAX

class MinStack {
private:
    // 栈必须是 long long，以防止差值溢出 int
    std::stack<long long> stk;
    // min_ele 也必须是 long long，以防止在 pop 恢复时溢出
    long long min_ele; 

public:
    MinStack() {
        // 构造函数
    }
    
    // O(1)
    void push(int val_int) {
        long long val = (long long)val_int; // 转换为 long long

        if (stk.empty()) {
            // 解释：第一个元素，差值为 0，最小值为 val
            stk.push(0LL);
            min_ele = val;
        } else {
            // 解释：计算 val 和当前最小值的差值
            long long diff = val - min_ele;
            stk.push(diff);
            
            if (diff < 0) {
                // 解释：如果 val 更小 (diff < 0)，则 val 成为新的最小值
                min_ele = val;
            }
        }
    }
    
    // O(1)
    void pop() {
        if (stk.empty()) return;

        long long diff = stk.top();
        stk.pop();

        if (diff < 0) {
            // 解释：如果 diff < 0，说明我们弹出了最小值。
            // 必须恢复到上一个最小值。
            // min_ele_old = min_ele_new - diff
            min_ele = min_ele - diff;
        }
    }
    
    // O(1)
    int top() {
        long long diff = stk.top();

        if (diff < 0) {
            // 解释：如果 diff < 0，说明栈顶元素就是当前最小值
            return (int)min_ele;
        } else {
            // 解释：否则，栈顶元素是 min_ele + diff
            return (int)(min_ele + diff);
        }
    }
    
    // O(1)
    int getMin() {
        return (int)min_ele;
    }
};

队列

队列是一种先进先出（FIFO）的数据结构，支持基本操作：入队（enqueue）、出队（dequeue）和查看队首元素（front）。队列的应用场景包括广度优先搜索、任务调度等。

我们可以使用容器适配器 std::queue 来实现队列, 也可以使用 std::deque 来实现双端队列。

对于 queue, 主要用到的接口有: push(), pop(), front(), back(), empty(), size(). 并且需要注意的是, queue 没有迭代器, 不能使用范围for循环来遍历queue中的元素, 只能通过不断 pop 出队列的方式来访问每个元素.

而对于 deque, 由于它是双端队列，可以分别操作两端，因此在入队和出队时要加以说明, 主要用到的接口有: push_back(), push_front(), pop_back(), pop_front(), front(), back(), empty(), size().

单调队列

单调队列是一种特殊的队列数据结构，它在入队和出队操作时保持队列内元素的单调性（从队头到队尾递增或递减）。其核心思想，是在 O(n) 的一次遍历中，为数组中的每一个元素，快速找到它左侧或右侧(取决于遍历方向)的第一个比它“大”（或“小”）的元素。

单调队列的应用场景包括滑动窗口问题、最大值/最小值查询等。

On this page
  1. 栈
    1. 邻项消除 & 合法括号字符串
    2. 单调栈
      1. 1. 基础：寻找下一个更大/更小元素 (NGE/NSE)
      2. 2. 进阶：柱状图中的最大矩形面积
      3. 最小字典序：移掉 K 位数字
    3. 例题: 最小栈
  2. 队列
    1. 单调队列