CS-Notes 题解精讲：栈与队列六道 Leetcode 经典题与单调栈模板

本文基于 CS-Notes 仓库中 Leetcode 题解 - 栈和队列 一篇整理，完整覆盖该文档收录的 6 道栈和队列题目（232、225、155、20、739、503）的 Java 解法，并结合仓库内 剑指 Offer 题解、算法 - 栈和队列 等文档，补充数据结构实现基础、复杂度分析和单调栈模板的归纳。读完后，你应能熟练写出“栈与队列相互模拟”“最小值栈”“括号匹配”三类基础题，并掌握单调栈处理“下一个更大元素”系列问题的通用套路。

题目总览

原文档收录的题目及难度如下，全部基于 Leetcode 题号：

题号	题目	难度	核心考点
232	Implement Queue using Stacks	Easy	双栈反转实现 FIFO
225	Implement Stack using Queues	Easy	队列首插维护 LIFO
155	Min Stack	Easy	辅助栈同步维护最小值
20	Valid Parentheses	Easy	栈顶配对与失配判断
739	Daily Temperatures	Medium	单调栈求下一个更大元素距离
503	Next Greater Element II	Medium	循环数组 + 单调栈倍增技巧

这些题目在仓库的 Leetcode 题解 - 目录 中被归类到“数据结构相关”板块下的栈和队列章节。下面先简单回顾两种数据结构的实现基础，再逐题展开。

基础回顾：栈与队列的实现方式

栈遵循后进先出（LIFO），队列遵循先进先出（FIFO）。在写题之前，理解两者底层实现有助于判断操作的时间成本。仓库中 算法 - 栈和队列 一文给出了完整的自研实现，可作为背景参考：

• 数组实现栈：维护元素数组和数量 N，push 时 a[N++] = item，pop 时 a[--N] 并置空释放引用；当 N 达到数组长度时扩容一倍，当 N 缩到四分之一时缩容一半，从而获得均摊 O(1) 的 push/pop。
• 链表实现栈：使用头插法，push 时新建节点并把 next 指向原 top，pop 时直接移动 top 指针。
• 链表实现队列：维护 first 与 last 指针，first 指向队首，出队时 first = first.next，入队时挂到 last 之后。

在 Leetcode 中则直接使用 Java 标准库：Stack<Integer> 提供 push/pop/peek，Queue<Integer> 用 LinkedList 承接，poll/peek/add/remove 分别对应不抛异常的出队、查看队首、入队与抛异常的出队。注意 remove() 与 poll() 的区别——前者在空队列时抛异常，后者返回 null，这也是 232 题 empty() 判断必须先于出队操作的原因。

1. 用栈实现队列（232）

栈的顺序为后进先出，而队列的顺序为先进先出。原文档给出的思路是：使用两个栈实现队列，一个元素需要经过两个栈才能出队列，在经过第一个栈时元素顺序被反转，经过第二个栈时再次被反转，此时就是先进先出顺序。

完整解法（继承自原文档）：

class MyQueue {

    private Stack<Integer> in = new Stack<>();
    private Stack<Integer> out = new Stack<>();

    public void push(int x) {
        in.push(x);
    }

    public int pop() {
        in2out();
        return out.pop();
    }

    public int peek() {
        in2out();
        return out.peek();
    }

    private void in2out() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
    }

    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

复杂度分析：push 直接进 in 栈，O(1)；pop/peek 只有在 out 栈为空时才触发整体搬运，均摊来看每个元素最多经历“进 in 栈、搬进 out 栈、出 out 栈”三次移动，因此 push、pop、peek 的均摊时间复杂度均为 O(1)，空间 O(n)。

与剑指 Offer 9 的对照：仓库中 9. 用两个栈实现队列 是同一题型的面试版本，其实现把搬运逻辑内联在 pop 中，并在两个栈都为空时抛出 queue is empty 异常。两者思路一致：in 栈处理入队，out 栈处理出队，两次反转恰好还原入队顺序。剑指版本还给出了一点工程经验——出队前必须检查 out.isEmpty() 且搬运后仍为空的情况，避免对空栈调用 pop。

2. 用队列实现栈（225）

反向的模拟：队列默认只能尾入首出，要让 push 的元素 x 出现在队列首部（保证 top/pop 的后进先出），就需要在 x 插入队尾后，把除 x 之外的所有元素“绕一圈”重新排到 x 之后。原文档的解法：

class MyStack {

    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    public void push(int x) {
        queue.add(x);
        int cnt = queue.size();
        while (cnt-- > 1) {
            queue.add(queue.poll());
        }
    }

    public int pop() {
        return queue.remove();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

复杂度分析：push 需要执行当前队列长度减一次的出队再入队操作，时间 O(n)；pop 和 top 都是直接操作队首，O(1)。这里体现了与 232 题相反的取舍——把成本集中在写入端。若改用“两个队列 + 出栈时整体搬运”的对称写法，则可以把成本转移到 pop 端，均摊 O(1)，这与 232 题的双栈结构完全对偶，从两题的对照可以看出：用一种结构模拟另一种，本质都是借助中转容器做“整体反转”。

实现细节上注意两点：

1. queue.remove() 与 queue.poll()：栈语义中 pop 空栈是未定义行为，Leetcode 保证调用合法，因此用会抛异常的 remove() 更贴合语义，与 232 中防御式编程形成对比；
2. while (cnt-- > 1) 保留了新元素 x 本身不参与旋转，保证它最终停在队首，这是“首插”的正确性关键。

3. 最小值栈（155）

155 题要求 O(1) 时间获取栈内最小值。原文档的做法是维护一个与 dataStack 同步增长的 minStack，每次 push 时把“截至当前的最小值”快照压入 minStack：

class MinStack {

    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;
    private int min;

    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
        min = Integer.MAX_VALUE;
    }

    public void push(int x) {
        dataStack.add(x);
        min = Math.min(min, x);
        minStack.add(min);
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
        min = minStack.isEmpty() ? Integer.MAX_VALUE : minStack.peek();
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

这样 push、pop、top、getMin 全部 O(1)，代价是空间 O(n)。

与剑指 Offer 30 的对照：仓库中 30. 包含 min 函数的栈 是同一题型的另一个版本，其 minStack 的写入方式写作 minStack.push(minStack.isEmpty() ? node : Math.min(minStack.peek(), node))，语义与 155 题完全等价——minStack 的第 k 个元素就是 dataStack 前 k 个元素的最小值。两个实现都采用“快照式”辅助栈，pop 时两栈同步弹出即可还原上一状态。

衍生问题：原文档最后还指出，对于“最小值队列”问题，可以先用栈实现队列（即 232 题），再将问题转换为最小值栈，这个组合技巧出自《编程之美》3.7 节。这提示了一个通用的解题策略：复合容器问题可以拆成“外层结构转换 + 内层结构增强”两步。

4. 用栈实现括号匹配（20）

给定只含 (、)、{、}、[、] 的字符串，判断括号是否有效。示例：

Input : "()[]{}"
Output: true

原文档的解法是“左括号入栈，右括号弹栈配对”：

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            char cStack = stack.pop();
            boolean b1 = c == ')' && cStack != '(';
            boolean b2 = c == ']' && cStack != '';
            boolean b3 = c == '}' && cStack != '{';
            if (b1 || b2 || b3) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

正确性要点：

• 遇到右括号时若栈为空，说明没有可配的左括号，直接返回 false；
• 弹出栈顶后若与当前右括号不匹配（b1/b2/b3 任一为真），返回 false；
• 遍历结束后栈必须为空，否则存在多余左括号。

时间 O(n)，空间 O(n)。原文档使用三个布尔量逐一枚举失配情形，等价的紧凑写法是用 Map<Character, Character> 存右括号到左括号的映射，一次 map.get(c) 查表比较即可，二者本质相同，面试时按个人习惯选择即可。

相关题型：仓库中 [31. 栈的压入、弹出序列 同样依赖“栈模拟”思想——用真实栈按压入序列 push，每次 push 后循环检查栈顶是否等于弹出序列的当前期望值，是“按顺序消费栈操作”这一模式的典型练习，可与本题一起掌握。

5. 下一个更大元素 I：每日温度（739）

给定温度数组，对每个位置求“下一个比它大的元素距离它多远”。示例：

Input : [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]

原文档的思路：在遍历数组时用栈把数组中的数（实际是下标）存起来，如果当前遍历的数比栈顶元素大，说明栈顶元素的下一个比它大的数就是当前元素。完整解法：

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] dist = new int[n];
    Stack<Integer> indexs = new Stack<>();
    for (int curIndex = 0; curIndex < n; curIndex++) {
        while (!indexs.isEmpty() && temperatures[curIndex] > temperatures[indexs.peek()]) {
            int preIndex = indexs.pop();
            dist[preIndex] = curIndex - preIndex;
        }
        indexs.add(curIndex);
    }
    return dist;
}

不变量分析：栈中保存的是下标，且对应温度呈单调不增（从栈底到栈顶递减）。每个元素只入栈一次、出栈一次，总操作 O(n)，因此时间 O(n)，空间 O(n)。若循环结束后栈中仍有下标，说明这些位置不存在更大的后续元素，dist 默认值 0 恰好是答案——这也是“先初始化结果数组为默认值”这一技巧的体现。

为什么存下标而不是值：题目要求的是距离（下标差），且值可能重复，用下标能同时解决取值与求差两个问题。这是单调栈题的通用习惯。

6. 循环数组中的下一个更大元素（503）

与 739 不同，503 题中数组是循环的，且求的是下一个更大元素本身而非距离：

Input : [1, 2, 1]
Output: [2, -1, 2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number;
The second 1's next greater number needs to search circularly, which is also 2.

原文档的解法用“倍增 + 取模”把循环数组展开成一轮半的线性扫描：

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] next = new int[n];
    Arrays.fill(next, -1);
    Stack<Integer> pre = new Stack<>();
    for (int i = 0; i < n * 2; i++) {
        int num = nums[i % n];
        while (!pre.isEmpty() && nums[pre.peek()] < num) {
            next[pre.pop()] = num;
        }
        if (i < n) {
            pre.push(i);
        }
    }
    return next;
}

关键细节：

1. 遍历 2n 次并用 i % n 取元素：相当于把数组复制一份拼在后面（a + a），让末尾元素也能找到“循环到开头”的更大元素，而不必真的复制数组；
2. 只在 i < n 时入栈：第二圈遍历时不再压入新下标，因为每个下标的答案在第一圈已经确定（要么被弹出赋值，要么最终为 -1）；若继续压栈会导致下标越界写 next 数组；
3. Arrays.fill(next, -1) 先置默认值：找不到的元素（如示例中的 2）保持 -1。

时间 O(n)（栈操作总数不超过 2n），空间 O(n)。

单调栈模板归纳与延伸

把 739 和 503 放在一起看，它们共享同一个骨架——维护单调不增栈，用“当前元素”去兑现“栈顶元素”的承诺：

// 栈存下标，栈内对应值单调不增
for (int i = 0; i < len; i++) {
    int cur = arr[i % n];              // 503 用取模实现循环，739 中 len = n
    while (!stack.isEmpty() && arr[stack.peek()] < cur) {
        int pre = stack.pop();
        answer[pre] = /* 用 cur 或 i 填写答案 */;
    }
    if (i < n) stack.push(i);         // 防止重复入栈
}

变体差异只在三处：数组是否循环（倍增取模）、答案是距离还是值、比较用 < 还是 <=（是否要求严格更大）。掌握这个模板后，同类的“下一个更大/更小元素”“柱状图最大矩形”等问题都是填空。

与“窗口 + 单调”相关的一道题是 59. 滑动窗口的最大值，仓库中该篇给出的解法是维护大小为窗口 M 的大顶堆：窗口右移时删除离开窗口的元素、加入新元素，单步 O(log M)，总时间 O(N log M)、空间 O(M)。对比可见：单调栈适合“扫描求承诺”型问题（严格 O(n)），堆适合“滑动窗口动态维护极值”型问题，两者在窗口场景下是两条可替换的技术路线，选择取决于是否需要 O(n) 严格线性时间。

复杂度小结与练习建议

题目	push/push 端成本	其他操作	空间
232 双栈队列	O(1)	pop/peek 均摊 O(1)	O(n)
225 队列栈	O(n)	pop/top O(1)	O(n)
155 最小值栈	O(1)	pop/top/getMin O(1)	O(n)
20 括号匹配	单遍 O(n)	—	O(n)
739 每日温度	单遍 O(n)	—	O(n)
503 循环下一更大	2n 遍历 O(n)	—	O(n)

练习路径建议按原文档的题号顺序推进：先完成 232/225 两个对偶模拟题（理解“反转还原 FIFO”），再做 155 与 剑指 Offer 30 对照（辅助栈同步），接着 20 括号匹配（栈顶配对的失败分支枚举），最后 739 → 503 完成单调栈模板的两次变体。全部题解代码均可在 Leetcode 题解 - 栈和队列 中核对，底层栈队列实现可参考 算法 - 栈和队列，更多 Leetcode 分类题解见 Leetcode 题解 - 目录。