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

这一课你将能做到

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();
    }
}