栈模块 — LeetCode 热门 100 题精讲（Java 向）

栈思想概述

栈（Stack）是一种后进先出（LIFO）的数据结构，其核心操作是入栈（push）、出栈（pop）和查看栈顶（peek）。在算法题中，栈的应用场景可归结为三类：

匹配与校验：利用栈的"抵消"特性，如括号匹配、字符串消消乐。
状态保存与回溯：保存历史上下文，如最小栈、字符串解码中的多层嵌套。
单调栈：维护栈内元素单调递增或递减，快速求解"下一个更大/更小元素"或"柱状图最大矩形"等问题。

LeetCode 热门 100 题中有五道栈经典题：20. 有效的括号（匹配校验）、155. 最小栈（状态保存）、394. 字符串解码（嵌套回溯）、739. 每日温度（单调栈基础）、84. 柱状图中最大的矩形（单调栈进阶）。下面逐一拆解。

1. 有效的括号（LeetCode 20）

题目：给定只包含 '(', ')', '{', '}', '[', ']' 的字符串，判断括号是否有效（左括号必须用相同类型右括号闭合，且正确嵌套）。

核心思路：遇到左括号入栈，遇到右括号则弹出栈顶并检查是否匹配。若最后栈为空则有效。

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> map = Map.of(')', '(', '}', '{', ']', '[');
    for (char c : s.toCharArray()) {
        if (map.containsKey(c)) {
            if (stack.isEmpty() || stack.pop() != map.get(c)) return false;
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

复杂度：时间 O(n)，空间 O(n)。

关键点：用 Deque 代替 Stack（Java 官方推荐）；右括号出现时栈顶必须匹配；最后检查栈是否为空，防止多出左括号。

2. 最小栈（LeetCode 155）

题目：设计一个支持 push、pop、top 和在常数时间内检索最小元素的栈（getMin）。

核心思路：维护两个栈，一个普通栈存所有元素，另一个单调栈存当前最小值（每次入栈时，若新元素小于等于当前最小值则同步入最小栈；出栈时若出栈元素等于最小栈顶则同步出栈）。

class MinStack {
    private Deque<Integer> stack;
    private Deque<Integer> minStack;
    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    public void pop() {
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}

复杂度：所有操作 O(1)，空间 O(n)。

关键点：入栈时用 <= 而非 <，避免重复最小值丢失；出栈比较要用 equals。

3. 字符串解码（LeetCode 394）

题目：给定编码字符串 k[encoded_string]，表示 encoded_string 重复 k 次，解码展开。如 3[a2[c]] → accaccacc。

核心思路：使用两个栈，一个存数字（重复次数），一个存当前构建的字符串前缀。

public String decodeString(String s) {
    Deque<Integer> countStack = new ArrayDeque<>();
    Deque<StringBuilder> strStack = new ArrayDeque<>();
    StringBuilder current = new StringBuilder();
    int k = 0;
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            k = k * 10 + (c - '0');
        } else if (c == '[') {
            countStack.push(k);
            strStack.push(current);
            current = new StringBuilder();
            k = 0;
        } else if (c == ']') {
            int repeat = countStack.pop();
            StringBuilder prev = strStack.pop();
            while (repeat-- > 0) prev.append(current);
            current = prev;
        } else {
            current.append(c);
        }
    }
    return current.toString();
}

复杂度：时间 O(n * maxK)，空间 O(n)。

关键点：数字可能有多位，需要连续累加；遇到 [ 时保存当前状态，重置后处理嵌套。

4. 每日温度（LeetCode 739）

题目：给定每日温度数组，返回数组 answer[i]，表示第 i 天需要等待多少天才能遇到更高温度；如果之后没有更高温度则填入 0。

核心思路：维护一个单调递减栈（栈底到栈顶温度递减）。从左向右遍历，当当前温度大于栈顶对应温度时，弹出栈顶并记录差值；否则入栈。

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] ans = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            ans[idx] = i - idx;
        }
        stack.push(i);
    }
    return ans;
}

复杂度：时间 O(n)，空间 O(n)。

关键点：栈内存的是下标；while 循环确保当前温度大于栈顶温度时，栈顶元素的下一个更高温度就是当前 i。

5. 柱状图中最大的矩形（LeetCode 84）

题目：给定非负整数数组 heights，求柱状图中能勾勒出的最大矩形面积。

核心思路：单调递增栈（找左右两侧第一个比当前柱子矮的位置）。遍历时，当 heights[i] < heights[stack.peek()] 时，弹出栈顶，并以该弹出柱子为矩形高度，右边界为 i，左边界为新的栈顶，计算面积。为了统一处理，在数组首尾添加高度为 0 的哨兵。

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] newHeights = new int[n + 2];
    System.arraycopy(heights, 0, newHeights, 1, n);
    Deque<Integer> stack = new ArrayDeque<>();
    int maxArea = 0;
    for (int i = 0; i < newHeights.length; i++) {
        while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
            int height = newHeights[stack.pop()];
            int width = i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

复杂度：时间 O(n)，空间 O(n)。

关键点：哨兵（首尾 0）避免了处理空栈和边界判断；当遇到更矮柱子时，说明栈顶柱子的右边界确定，左边界为弹出后的新栈顶；计算宽度为 right - left - 1。

五题对比与总结

题目	栈类型	核心操作	时间复杂度	空间复杂度	关键难点
有效的括号	基础匹配	入栈/出栈匹配	O(n)	O(n)	左右括号映射
最小栈	状态保存	双栈同步	O(1)	O(n)	最小值栈同步逻辑
字符串解码	嵌套回溯	双栈 + 字符串拼接	O(n * maxK)	O(n)	数字累加与嵌套恢复
每日温度	单调栈	维护递减栈	O(n)	O(n)	下标记录与差值计算
柱状图最大矩形	单调栈（进阶）	维护递增栈 + 哨兵	O(n)	O(n)	左右边界确定与面积公式

共同本质：栈的核心价值在于 “保存等待处理的状态”。括号匹配等待右括号来抵消；最小栈等待元素出栈时同步更新最小值；字符串解码等待 ] 来触发重复；单调栈等待一个破坏单调性的元素来触发面积/温度计算。

总结心法：

需要 成对抵消 或匹配 → 基础栈。
需要 保存当前环境状态 供后续回溯 → 多栈配合。
需要求 下一个更大/更小元素 → 单调栈（存下标）。
需要求 连续区间最值或面积 → 单调栈 + 左右边界计算（通常用哨兵简化）。