算法面试突击手册 —— 栈与单调栈

一、概念与特点

大白话 + 类比

普通栈 = 餐厅的盘子叠

后洗好的盘子摞在最上面（后进先出，LIFO）。你要拿盘子，只能从最上面取。

单调栈 = 一条有身高鄙视链的排队通道

想象一群人排队进电梯，每个人都向前看。如果前面的人比自己矮，就把矮子挤走（弹出），直到前面的人比自己高为止。这样队伍始终从高到矮排列——这就是单调递减栈。反过来就是单调递增栈。

单调栈的精髓在于：每个元素进栈前，先清掉前面所有不如自己的。这样栈内始终保持单调，而每个元素也能同步知道”左边/右边第一个比自己大/小的元素”是谁。

核心特征（什么时候该想到用它）

特征说明
括号匹配”{[( )]}” 类问题，后出现的右括号要匹配最近的左括号
”下一个更大元素”每日温度、下一个更大元素系列
”最近/最远” + 大小关系找左边第一个比当前小/大的
柱状图/直方图最大面积单调栈 + 哨兵
嵌套结构字符串解码（括号嵌套）

识别信号词

  • “括号”、“有效括号” → 栈匹配
  • “下一个更大/更小”、“每日温度” → 单调栈
  • “最近的最小值”、“最小栈” → 辅助栈
  • “解码”、“展开”、“嵌套” → 双栈模拟

二、应用场景

单调栈通用模板

// 单调递减栈（找下一个更大元素）
// 栈内存下标，对应值严格递减
for (int i = 0; i < n; i++) {
    // 当前元素比栈顶大 → 栈顶元素找到了"下一个更大元素"
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        int idx = stack.pop();
        result[idx] = i - idx; // 或者 nums[i]
    }
    stack.push(i);
}

// 单调递增栈（找下一个更小元素）
for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
        int idx = stack.pop();
        result[idx] = i - idx;
    }
    stack.push(i);
}

三、Hot 100 精讲题目

20. Valid Parentheses 有效的括号

📌 给定只包含 () [] {} 的字符串，判断是否有效。有效条件：左右括号类型匹配，嵌套顺序正确。如 "()[]{}" → true，"([)]" → false

🔍 解题分析

为什么用栈：右括号必须匹配最近出现的未匹配的左括号——这正是”后进先出”。

核心思路：

  1. 遍历字符串
  2. 遇到左括号 → 压入栈
  3. 遇到右括号 → 检查栈顶是否是对应的左括号
    • 不是或栈为空 → false
    • 是 → 弹出栈顶
  4. 遍历完检查栈是否为空

技巧：用 HashMap 建立 右括号 → 左括号 的映射，避免写三个 if。

✅ 完整 Java 实现

public boolean isValid(String s) {
    // 右括号 → 左括号映射
    Map<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put(']', '[');
    map.put('}', '{');

    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (map.containsKey(c)) {
            // 是右括号：栈顶必须匹配
            if (stack.isEmpty() || stack.peek() != map.get(c)) {
                return false;
            }
            stack.pop();
        } else {
            // 是左括号：压入栈
            stack.push(c);
        }
    }

    return stack.isEmpty(); // 栈为空说明全部匹配
}

⏱ 复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

💡 记忆口诀

“左括号进栈，右括号找最近的左括号配对退栈”

155. Min Stack 最小栈

📌 设计一个栈，支持 push、pop、top 和常数时间获取最小值 getMin。

🔍 解题分析

核心思路（辅助栈）：用一个额外的栈 minStack，其栈顶始终是当前主栈中的最小值。

操作：

  • push(x)：主栈压入 x；若 minStack 为空或 x <= minStack.peek()，minStack 也压入 x
  • pop()：主栈弹出；若弹出值 == minStack 栈顶，minStack 也弹出
  • getMin()：返回 minStack 栈顶

为什么相等也压入：处理重复最小值的情况，x <= minStack.peek() 使用 <= 确保重复最小值的正确性。

✅ 完整 Java 实现

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);
        // 如果 minStack 为空，或 val 比当前最小值还小（或相等）
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        // 如果弹出的正好是最小值，minStack 也同步弹出
        if (stack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        stack.pop();
    }

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

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

⏱ 复杂度分析

  • 时间复杂度：所有操作 O(1)
  • 空间复杂度：O(n)

💡 记忆口诀

“双栈同步走，最小值栈顶守”

394. Decode String 字符串解码

📌 "3[a2[c]]" → "accaccacc"。方括号可以嵌套。

🔍 解题分析

为什么用栈：括号嵌套是栈的经典场景。数字、字符串可能嵌套多层。

核心思路（双栈法）：

  1. numStack 存数字（重复次数），strStack 存当前已解析的字符串
  2. 遍历字符：
    • 数字：累加到 currentNum
    • 左括号 [：把 currentNum 和 currentStr 分别压栈，然后重置
    • 字母：追加到 currentStr
    • 右括号 ]：从 numStack 弹出次数 k，将 currentStr 重复 k 次，再和 strStack 弹出的前缀字符串拼接

类比：遇到 [ 就像进入子任务，先把当前工作保存起来；遇到 ] 就像子任务完成，把保存的工作拿出来和子任务结果合并。

✅ 完整 Java 实现

public String decodeString(String s) {
    Deque<Integer> numStack = new ArrayDeque<>();   // 存重复次数
    Deque<StringBuilder> strStack = new ArrayDeque<>(); // 存外层字符串

    StringBuilder currentStr = new StringBuilder(); // 当前构建的字符串
    int currentNum = 0; // 当前读取的数字

    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            // 数字可能多位，如 "12"
            currentNum = currentNum * 10 + (c - '0');
        } else if (c == '[') {
            // 遇到 '['：保存当前状态，进入内层
            numStack.push(currentNum);
            strStack.push(currentStr);
            currentNum = 0;
            currentStr = new StringBuilder();
        } else if (c == ']') {
            // 遇到 ']'：内层结束，拼接结果
            int repeat = numStack.pop();
            StringBuilder innerStr = currentStr; // 内层重复的内容
            currentStr = strStack.pop(); // 取出外层字符串前缀

            // 把内层内容重复 repeat 次拼接到外层
            for (int i = 0; i < repeat; i++) {
                currentStr.append(innerStr);
            }
        } else {
            // 普通字母：直接追加
            currentStr.append(c);
        }
    }

    return currentStr.toString();
}

⏱ 复杂度分析

  • 时间复杂度：O(n × maxRepeat)，最坏情况所有字符被复制多次
  • 空间复杂度：O(n)，栈深度

💡 记忆口诀

“遇左括号存现场，遇右括号取回来重复拼接”

739. Daily Temperatures 每日温度

📌 给定每日气温数组 T，返回数组 answer，answer[i] 表示需要等待几天才会有更高温度。如果没有，填 0。如 [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]

🔍 解题分析

为什么用单调栈：对每个元素，要找右边第一个比它大的元素的距离。单调递减栈是标准解法。

核心思路：

  1. 维护单调递减栈（存下标，对应温度递减）
  2. 遍历每天的温度
  3. 当前温度比栈顶温度高时 → 栈顶元素找到了”下一个更高温度”的日子
  4. 弹出栈顶，计算天数差 i - stackTop
  5. 当前下标入栈（继续等待它的更高温度）

类比：栈里的每一天都在”排队等升温”。新来的如果温度更高，就把队里所有比它凉快的天都弹出来——这些天终于等到更热的日子了。

✅ 完整 Java 实现

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];

    // 单调递减栈，存下标（对应温度严格递减）
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        // 当前温度比栈顶高 → 栈顶找到了下一个更高温
        while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
            int prevDay = stack.pop();
            answer[prevDay] = i - prevDay; // 等待天数
        }
        stack.push(i);
    }

    // 留在栈里的下标没有找到更高温度，answer 默认为 0
    return answer;
}

⏱ 复杂度分析

  • 时间复杂度：O(n)，每个下标入栈出栈各一次
  • 空间复杂度：O(n)

💡 记忆口诀

“栈里排队等升温，新人来了挤走凉快的前辈”

84. Largest Rectangle in Histogram 柱状图中最大的矩形

📌 给定柱子高度数组 heights，求柱状图中能勾勒出的最大矩形面积。如 [2,1,5,6,2,3] → 10

🔍 解题分析

为什么用单调栈：对每根柱子，要找到以它为高的矩形的最大宽度。宽度 = 右边第一个比它矮的位置 - 左边第一个比它矮的位置 - 1。单调递增栈正好能同时找到左右边界。

核心思路：

  1. 在数组两端加哨兵（高度 0），简化边界处理
  2. 维护单调递增栈（存下标，对应高度递增）
  3. 当前高度 < 栈顶高度时 → 栈顶的右边界出现了
  4. 弹出栈顶，计算以它为高的最大矩形面积：
    • 高 = heights[stackTop]
    • 宽 = i - stack.peek() - 1（新栈顶是左边界，i 是右边界）

类比：栈里的柱子越来越高。来了一根矮柱子，它成了前面所有高柱子的”右围墙”。每根高柱子的左围墙就是栈里它前面的那个柱子。

✅ 完整 Java 实现

public int largestRectangleArea(int[] heights) {
    int n = heights.length;

    // 构建带哨兵的高度数组：两端各加一个高度 0
    int[] newHeights = new int[n + 2];
    System.arraycopy(heights, 0, newHeights, 1, n);
    // newHeights[0] = 0, newHeights[n+1] = 0

    Deque<Integer> stack = new ArrayDeque<>(); // 单调递增栈，存下标
    int maxArea = 0;

    for (int i = 0; i < newHeights.length; i++) {
        // 当前高度 < 栈顶高度 → 栈顶找到了右边界，可以计算面积
        while (!stack.isEmpty() && newHeights[stack.peek()] > newHeights[i]) {
            int h = newHeights[stack.pop()]; // 以这根柱子为高
            int w = i - stack.peek() - 1;    // 左边界是再前面那根，右边界是 i
            maxArea = Math.max(maxArea, h * w);
        }
        stack.push(i);
    }

    return maxArea;
}

⏱ 复杂度分析

  • 时间复杂度：O(n)，每个下标入栈出栈一次
  • 空间复杂度：O(n)

💡 记忆口诀

“两边加 0 做哨兵，高柱子遇矮柱子就弹出算面积”

32. Longest Valid Parentheses 最长有效括号

📌 给定只含 ( 和 ) 的字符串，找出最长有效括号子串的长度。如 ")()())" → 4（"()()"）

🔍 解题分析

方法一：栈（推荐）

  • 栈底始终保留最后一个未匹配的右括号的下标（或 -1 作为初始标记）
  • 遇到 ( 压栈
  • 遇到 ) 弹栈：
    • 弹完后栈不为空：当前有效长度 = i - stack.peek()
    • 弹完后栈为空：当前右括号是非法分隔符，把 i 压栈作为新的标记

方法二：双向扫描（无需栈，O(1) 空间）

  • 左到右扫描：统计 left 和 right 数量，相等时算长度，right > left 时归零
  • 右到左扫描：同理，处理 (() 这类被截断的情况

✅ 完整 Java 实现

// 方法一：栈（更直观）
public int longestValidParentheses(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1); // 初始哨兵，表示最后一个无效位置
    int maxLen = 0;

    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop(); // 弹出最近的 '(' 或无效标记

            if (stack.isEmpty()) {
                // 栈空了，说明当前的 ')' 无效，把它作为新的无效标记
                stack.push(i);
            } else {
                // 计算当前有效长度
                maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }

    return maxLen;
}

// 方法二：双向扫描（O(1) 空间）
public int longestValidParentheses_O1(String s) {
    int left = 0, right = 0, maxLen = 0;

    // 左 → 右
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') left++;
        else right++;

        if (left == right) maxLen = Math.max(maxLen, 2 * right);
        else if (right > left) { left = 0; right = 0; }
    }

    // 右 → 左
    left = 0; right = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == '(') left++;
        else right++;

        if (left == right) maxLen = Math.max(maxLen, 2 * left);
        else if (left > right) { left = 0; right = 0; }
    }

    return maxLen;
}

⏱ 复杂度分析

  • 时间复杂度：栈方法 O(n)，双向扫描 O(n)
  • 空间复杂度：栈方法 O(n)，双向扫描 O(1)

💡 记忆口诀

“栈底存最后无效位置，左右数量相等时算长度”

🔜 上一章：04-前缀和 | 下一章：06-二分查找