栈：专治「最近的、未匹配的」

这一课你将能做到

1. 识别「括号匹配、嵌套消除、下一个更大元素」三类栈的信号题
2. 写出有效括号的映射判法和每日温度的「单调栈」解法
3. 说清单调栈里存的是什么、元素何时入栈何时出栈

为什么要学

栈是规则最简单的数据结构：后进先出（LIFO），像一摞盘子，只能从顶上放、从顶上拿。规则简单到初学者会怀疑它有什么用——它的全部威力在于一个直觉：「最近放进去、还没处理完的东西，永远最先被需要」。

函数调用靠栈（调用链一层层返回）、编辑器的撤销靠栈、浏览器后退靠栈、编译器检查括号也靠栈。算法面试里，凡是题目读起来有「匹配」「嵌套」「往回看找第一个……」的味道，十有八九是栈。它代码短、模板固定，是必拿分的题型。

先建立图像

压栈 push → [底]  A  B  C  [顶] ← 弹栈 pop（C 先出）
                       ↑
                    peek 只看不拿

两种考法的直觉：

题目味道	栈里放什么	动作
括号配对、嵌套消除	未匹配的左括号 / 待消除元素	遇配对就弹出，最后栈空则合法
下一个更大 / 更暖的一天	「还没找到答案」的下标	遇到更大值时批量结算栈顶

第二种叫单调栈：栈里元素保持单调（本题是温度从栈底到栈顶递减），它是栈类中等题的核心套路。

跟着做

步骤 1：LeetCode 20「有效的括号」（简单）

给定只含 ()[]{} 的字符串，判断括号是否正确匹配，如 ()[]{} 合法、([)] 不合法。

思路：遇到左括号压栈；遇到右括号，它必须和栈顶那个左括号配对——栈空或类型不对，立即判错。走完整个字符串，栈必须是空的（每个左括号都有人匹配）。

import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isValid(String s) {
        // 右括号 -> 它应匹配的左括号
        Map<Character, Character> match = new HashMap<>();
        match.put(')', '(');
        match.put(']', '[');
        match.put('}', '{');

        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (match.containsKey(c)) {
                // 栈顶必须是对应的左括号
                if (stack.isEmpty() || stack.pop() != match.get(c)) {
                    return false;
                }
            } else {
                stack.push(c); // 左括号入栈，等未来的右括号来认领
            }
        }
        return stack.isEmpty();
    }
}

逐点讲：注意最后 return stack.isEmpty()，字符串 "(()" 遍历过程不报错，但栈里剩一个左括号，必须判为非法。时间 O(n)，空间 O(n)。

步骤 2：LeetCode 155「最小栈」（简单，体会辅助栈）

要求在 O(1) 时间内完成压栈、弹栈、取栈顶、取当前最小值。

思路：维护两个栈，一个正常存元素，另一个「单调不增」地存「每个时刻的最小值」。

import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
    private final Deque<Integer> data = new ArrayDeque<>();
    private final Deque<Integer> mins = new ArrayDeque<>();

    public MinStack() {
        mins.push(Integer.MAX_VALUE); // 哨兵，省去空栈判断
    }

    public void push(int val) {
        data.push(val);
        mins.push(Math.min(val, mins.peek())); // 新元素和当前最小取更小
    }

    public void pop() {
        data.pop();
        mins.pop();
    }

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

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

每个操作都是 O(1)，空间 O(n)。辅助栈思想在很多题里反复出现：用一个平行结构记录「额外维度」的信息。

步骤 3：LeetCode 739「每日温度」（中等，单调栈）

给定每日温度数组 temperatures，对每一天回答：还要等几天才会遇到更暖的温度？若之后都不会更暖，填 0。如 [73,74,75,71,69,72,76,73] 输出 [1,1,4,2,1,1,0,0]。

暴力对每天往后扫是 O(n²)。单调栈思路：栈里存放「还没等到更暖天气」的日期下标，且这些下标对应的温度从栈底到栈顶递减。今天温度一旦高于栈顶那天，栈顶那天的答案就被今天确定了，弹出并结算；新的一天入栈继续等。

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Deque<Integer> stack = new ArrayDeque<>(); // 存下标
        for (int today = 0; today < n; today++) {
            // 今天能「温暖」栈顶等待者，就连续结算
            while (!stack.isEmpty() && temperatures[today] > temperatures[stack.peek()]) {
                int waitingDay = stack.pop();
                answer[waitingDay] = today - waitingDay;
            }
            stack.push(today); // 今天开始等它的更暖日
        }
        return answer; // 始终没等到的位置保持 0
    }
}

逐点讲：每个下标最多入栈一次、出栈一次，所以总时间 O(n)，空间 O(n)。关键理解是 while 不是 if——一天可能同时「解放」好几个等待者（想象气温骤升）。

讲清楚要点

1. 栈处理的是「最近」关系：栈顶永远是最近入栈且尚未了结的元素，这正好对应括号和嵌套的语义。
2. 写栈题先问「栈里放元素还是放下标」：括号匹配放字符即可；每日温度要算天数差，必须放下标，这是最常见的实现岔路。
3. 单调栈的三步骨架：当前元素能结算栈顶就 while 弹出结算；结算不动了就把当前元素压栈；遍历结束留在栈里的按默认值处理。
4. Java 中用 ArrayDeque 当栈：push/pop/peek，比遗留的 Stack 类（继承 Vector、方法加锁）性能好，官方推荐。
5. 判空检查不能省：右括号比左括号多、栈空还 pop，是括号题第一大崩溃点。

你可能会懵的地方

• 为什么用 Deque 而不是 Stack？ java.util.Stack 是早期设计，继承 Vector，所有方法带 synchronized，单线程下白白加锁；ArrayDeque 更快、接口更干净，是现在的标准选择。

• 单调栈为什么是「递减」而不是递增？ 栈里是「还没等到更大值」的元素，如果栈里已有 75，又来一个 71，71 更小、不可能帮 75 等到答案，只能排在 75 后面一起等，所以天然递减。等一个大温度来了，从栈顶（最小的等待者）开始依次解放。

• while 弹栈时不怕漏掉谁吗？ 不怕。栈顶温度比今天低才弹，弹完看下一个；一旦栈顶温度 ≥ 今天，它下面的温度只会更高（递减栈），更不可能被今天解放，可以立刻停止。

• 遇到其他六种括号 / 单引号怎么办？ 往映射表里加对应条目即可，算法逻辑一字不改，这正是映射表写法的扩展性。

• 栈和递归能互换吗？ 能，递归本质就是调用栈。任何递归都可以改写成显式栈迭代，树和图的 DFS 就是这么来的，后续课程会见到。

错法对照

错法	问题	正解
括号题用 if 判断类型、不查栈空	右括号多时对空栈 pop 抛异常	先 isEmpty() 再比较
结尾直接 return true	"(()" 这类残留被误判合法	return stack.isEmpty()
每日温度栈里存温度值	算不出隔了几天	存下标，取温度时再去数组查
用 if 只结算一个栈顶	气温骤升时多个等待者漏结算	用 while 连续弹到不能弹
把新元素先压栈再比较	自己和自己比较	先 while 结算，再 push

卡点急救

1. 单调栈题看不懂题解：别盯代码，拿三天的小用例（如 [30,60,90]）手动模拟——每天谁在栈里、谁被弹出、答案填几，走一遍立刻通。
2. 下标越界 / 空栈异常：所有 pop/peek 前确认有 !isEmpty() 守卫，括号映射写法天然要先判空。
3. 不知道该递增栈还是递减栈：看目标。找「下一个更大」用递减栈（小的在顶等着被大的解放）；找「下一个更小」反过来。先背这个对应，再刷题内化。

面试常问

• 有效括号的变体：只有一种小括号但带通配符 * 怎么办（LeetCode 678）？ 思路升级为两个栈（或两个计数范围）：记录左括号可能的位置区间，通配符既可当左也可当右，用区间 [可能的最少左括号, 最多左括号] 维护，过程中区间下限不小于 0，结尾区间包含 0 即合法。考察的是把「精确匹配」放宽成「可能性范围」。

• 单调栈能解决哪些题？为什么它是 O(n)？ 下一个更大元素、每日温度、柱状图中最大矩形、接雨水等。每个元素入栈一次、出栈一次，总共不超过 2n 次操作，所以是 O(n)。

• 给一个嵌套的 JSON / HTML 标签串，怎么验证嵌套正确？ 同括号匹配：遇到开标签压栈，闭标签必须与栈顶同名后弹出，结束栈空。工程上解析器还会处理属性和转义字符，但嵌套校验的内核就是这个栈。

自测三问

1. 栈的 LIFO 特性对应了现实里哪类关系？举两个例子。
2. 每日温度的栈里为什么必须存下标而不是温度？
3. 有效括号遍历完不报错，为什么还不能直接返回 true？

小结一句话

凡涉及「最近、未匹配、往回看第一个更大/更小」的问题，栈顶就是答案所在；普通栈管匹配，单调栈管批量等待与结算。

延伸

• 巩固练习：LeetCode 496 下一个更大元素 I、LeetCode 150 逆波兰表达式求值、LeetCode 84 柱状图中最大的矩形
• 在本站在线判题平台提交时，试试只有左括号、只有右括号的极端用例
• 下一课预告：二分查找——在有序世界里每次排除一半，吃透边界写法和旋转数组