栈

Java大神2026/4/10大约 24 分钟常用算法题栈

本章题海战术

典型例题	leetcode题目	leetcode链接
有效的括号	leetcode 20	https://leetcode.cn/problems/valid-parentheses/description/
最小栈	leetcode 155	https://leetcode.cn/problems/min-stack/description/
每日温度	leetcode 739	https://leetcode.cn/problems/daily-temperatures/description/
逆波兰表达式求值	leetcode 150	https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
柱状图中最大的矩形	leetcode 84	https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
用栈实现一个队列	leetcode 232	https://leetcode.cn/problems/implement-queue-using-stacks/description/

栈

📚 栈的核心特性 & Java 实现规范

栈是 后进先出（LIFO） 的线性数据结构，所有插入、删除操作都只能在栈顶完成。

⚠️ 面试必踩基础坑：

不推荐使用 java.util.Stack：它继承自 Vector，方法默认加 synchronized 保证线程安全，性能差，且继承体系设计不规范。
大厂标准写法：使用 Deque 接口，实现类优先选 ArrayDeque（基于动态数组，读写性能最优）

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

栈操作示意图

✅ 高频题 1：有效的括号（LeetCode 20・简单）

题目：给定一个只包含 () [] {} 的字符串，判断括号是否有效。左括号必须用同类型右括号闭合，且顺序正确。

解题思路

遇到左括号，将对应的右括号压入栈
遇到右括号，判断栈是否为空、栈顶元素是否与当前右括号匹配
遍历结束后，栈为空则说明完全匹配

核心 Java 代码

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');
        else if (c == '[') stack.push(']');
        else if (c == '{') stack.push('}');
        // 遇到右括号，栈空或栈顶不匹配直接返回false
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();
}

💡 考点点睛

栈的经典匹配场景：嵌套、对称类问题优先考虑栈
时间复杂度 O (n)，空间复杂度 O (n)

📏 高频题 2：最小栈（LeetCode 155・中等）

题目：设计一个支持 push、pop、top 操作，并能在 O (1) 时间内检索到最小元素的栈。

解题思路

采用辅助栈同步主栈操作：

主栈存储正常元素
辅助栈存储「当前栈内的最小值」，每次 push 新元素时，比较新元素与辅助栈栈顶，将更小的值压入辅助栈
pop 时两个栈同步弹出，辅助栈栈顶永远是当前栈的最小值

双栈结构示意图

核心 Java 代码

class MinStack {
    Deque<Integer> mainStack;
    Deque<Integer> minStack;

    public MinStack() {
        mainStack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        mainStack.push(val);
        // 辅助栈压入当前最小值
        minStack.push(minStack.isEmpty() ? val : Math.min(val, minStack.peek()));
    }
    
    public void pop() {
        mainStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return mainStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

💡 考点点睛

空间换时间的经典设计题
进阶追问：如何优化辅助栈空间？（重复最小值只存一次，pop 时判断当前值是否等于最小值再弹出）

🌡️ 高频题 3：每日温度（LeetCode 739・中等）

题目：给定整数数组 temperatures 表示每日温度，返回数组 answer，answer[i] 表示第 i 天之后，下一个更高温度间隔的天数；无更高温度则为 0。

解题思路

单调递减栈（栈内下标对应的温度保持递减）：

栈中存储数组下标，保证下标对应温度单调递减
遍历每日温度：若当前温度 > 栈顶下标对应温度，说明找到了栈顶那天的下一个更高温，计算天数差并弹出栈顶；重复直到栈为空或当前温度不大于栈顶温度，再将当前下标压栈

单调栈执行示意（以 [73,74,75,71,69,72] 为例）

核心 Java 代码

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 prev = stack.pop();
            ans[prev] = i - prev;
        }
        stack.push(i);
    }
    return ans;
}

💡 考点点睛

单调栈模板题，「下一个更大元素」类问题的通用解法
时间复杂度 O (n)：每个元素最多入栈、出栈各一次
同类延伸题：下一个更大元素 I/II、接雨水

🧮 高频题 4：逆波兰表达式求值（LeetCode 150・中等）

题目：给定字符串数组 tokens 表示逆波兰表达式（后缀表达式），计算其值。有效运算符为 + - * /，操作数均为整数。

解题思路

后缀表达式天然适配栈结构：

遇到数字，压入栈
遇到运算符，弹出栈顶两个数（注意顺序：先弹出的是右操作数，后弹出的是左操作数），运算后将结果压回栈
遍历结束后，栈中剩余元素即为最终结果

核心 Java 代码

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String token : tokens) {
        if ("+-*/".contains(token)) {
            int b = stack.pop(); // 右操作数
            int a = stack.pop(); // 左操作数
            switch (token) {
                case "+": stack.push(a + b); break;
                case "-": stack.push(a - b); break;
                case "*": stack.push(a * b); break;
                case "/": stack.push(a / b); break;
            }
        } else {
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

💡 考点点睛

栈的经典应用场景：表达式求值、编译器语法分析
高频易错点：减法、除法的操作数顺序，先弹出的是右侧操作数

📊 高频题 5：柱状图中最大的矩形（LeetCode 84・困难）

题目：给定 n 个非负整数表示柱状图中每个柱子的高度，柱子宽度为 1，求柱状图中能勾勒出的矩形的最大面积。

解题思路

单调递增栈：

核心逻辑：对每个柱子，找到「左边第一个比它矮的柱子」和「右边第一个比它矮的柱子」，宽度 = 右下标 - 左下标 - 1，面积 = 高度 × 宽度
用单调递增栈存下标，遇到比栈顶小的元素时，栈顶元素的右边界就已确定，左边界为新的栈顶
技巧：首尾加 0 作为哨兵，统一边界处理，无需单独判断栈空

核心 Java 代码

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    // 首尾加0哨兵，统一边界判断
    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 h = newHeights[stack.pop()];
            int w = i - stack.peek() - 1;
            maxArea = Math.max(maxArea, h * w);
        }
        stack.push(i);
    }
    return maxArea;
}

💡 考点点睛

单调栈的困难级应用，大厂压轴题高频考点
哨兵技巧是面试加分项，能体现代码简洁性和边界处理能力
同类延伸题：最大矩形（LeetCode 85）

🎯 面试加分总结

栈的适用场景口诀：匹配类、嵌套类、下一个更大 / 更小类、表达式求值、消除类问题，优先考虑栈
单调栈通用规律：
- 找下一个更大元素 → 单调递减栈
- 找下一个更小元素 → 单调递增栈
Java 实现规范：永远用 Deque + ArrayDeque 替代 Stack 类，体现基础扎实度

核心代码 & 技术亮点标注

1. 有效的括号（LeetCode 20）

public boolean isValid(String s) {
    // ✅ 技术亮点1：用ArrayDeque替代Stack，无同步锁性能更高，符合Java官方推荐规范
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        // ✅ 技术亮点2：左括号直接压对应右括号，匹配时无需二次映射判断，省去哈希表开销
        if (c == '(') stack.push(')');
        else if (c == '[') stack.push(']');
        else if (c == '{') stack.push('}');
        // ✅ 技术亮点3：提前剪枝，栈空或不匹配直接返回，无需遍历剩余字符
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();
}

面试可讲亮点：

选型规范：摒弃过时的Stack类，采用Deque + ArrayDeque实现，避免 Vector 同步锁带来的性能损耗，体现 Java 基础扎实度
逻辑优化：左括号直接压入对应右括号，匹配阶段直接等值比较，代码简洁且无额外空间开销
提前终止：遇到不匹配立即返回，平均场景下时间效率优于完整遍历

2. 最小栈（LeetCode 155）

基础标准版

class MinStack {
    Deque<Integer> mainStack;
    Deque<Integer> minStack;

    public MinStack() {
        mainStack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        mainStack.push(val);
        // ✅ 技术亮点：辅助栈同步压入当前最小值，栈顶永远是全局最小值
        minStack.push(minStack.isEmpty() ? val : Math.min(val, minStack.peek()));
    }
    
    public void pop() {
        // ✅ 技术亮点：双栈严格同步弹出，保证最小值与主栈元素一一对应
        mainStack.pop();
        minStack.pop();
    }
    
    public int top() { return mainStack.peek(); }
    public int getMin() { return minStack.peek(); }
}

进阶空间优化版（面试加分代码）

// ✅ 技术亮点：重复最小值仅存一次，大幅节省辅助栈空间
public void push(int val) {
    mainStack.push(val);
    // 仅当新元素小于等于当前最小值时才压入辅助栈
    if (minStack.isEmpty() || val <= minStack.peek()) {
        minStack.push(val);
    }
}

public void pop() {
    int popVal = mainStack.pop();
    // 仅当弹出值等于当前最小值时，辅助栈才弹出
    if (popVal == minStack.peek()) {
        minStack.pop();
    }
}

面试可讲亮点：

设计思想：经典空间换时间，用辅助栈实现 O (1) 时间获取最小值
优化思维：重复最小值仅存储一次，极端场景（大量重复元素）下辅助栈空间节省 50% 以上
鲁棒性：基础版双栈同进同出，逻辑简单不易出错；优化版按需弹出，体现空间优化意识

3. 每日温度（LeetCode 739）

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] ans = new int[n];
    // ✅ 技术亮点1：栈存数组下标而非值，可同时获取温度值和计算间隔天数
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        // ✅ 技术亮点2：单调递减栈标准模板，while循环弹出所有可匹配的元素
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prev = stack.pop();
            ans[prev] = i - prev;
        }
        stack.push(i);
    }
    return ans;
}

面试可讲亮点：

模板化实现：标准单调递减栈写法，可无缝复用到所有「下一个更大元素」类问题
通用性设计：通过下标同时完成值比较和距离计算，无需额外封装对象
复杂度优势：每个元素仅入栈、出栈各一次，整体 O (n) 时间，远优于暴力 O (n²)

4. 逆波兰表达式求值（LeetCode 150）

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String token : tokens) {
        // ✅ 技术亮点1：字符串contains快速判断运算符，简化分支逻辑
        if ("+-*/".contains(token)) {
            // ✅ 技术亮点2：严格遵循「先弹右操作数、后弹左操作数」，规避减法除法顺序错误
            int b = stack.pop();
            int a = stack.pop();
            int res = switch (token) {
                case "+" -> a + b;
                case "-" -> a - b;
                case "*" -> a * b;
                case "/" -> a / b;
                default -> 0;
            };
            stack.push(res);
        } else {
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

面试可讲亮点：

结构适配：后缀表达式天然适配栈结构，无需处理运算符优先级，是栈的经典应用场景
易错点规避：明确操作数弹出顺序，从根源避免减法、除法的顺序错误
代码简洁性：用字符串匹配 + switch 分支，逻辑清晰易读

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

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    // ✅ 技术亮点1：首尾加0哨兵，统一边界处理，无需单独判断栈空情况
    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++) {
        // ✅ 技术亮点2：单调递增栈，遇到更小元素时确定栈顶元素的右边界
        while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
            int h = newHeights[stack.pop()];
            // ✅ 技术亮点3：宽度公式：右边界下标 - 左边界下标 - 1
            int w = i - stack.peek() - 1;
            maxArea = Math.max(maxArea, h * w);
        }
        stack.push(i);
    }
    return maxArea;
}

面试可讲亮点：

哨兵技巧：首尾添加高度为 0 的哨兵柱子，彻底规避栈空特判和首尾柱子的边界问题，代码简洁且不易出错
核心思想：一次遍历同时找到每个柱子的左右第一个更小边界，将暴力 O (n²) 优化到 O (n)
可复用性：宽度计算公式通用，所有「找左右边界求面积」类问题均可套用

🎯 栈类算法通用技术难点 & 解决方案汇总

技术难点	问题表现	解决方案	面试加分话术
栈实现类选型错误	误用`java.util.Stack`，性能差且继承体系不规范	统一使用`Deque`接口，实现类优先选`ArrayDeque`；`LinkedList`可作为备选但内存开销更大	Stack 是 JDK 早期遗留类，继承自 Vector 自带同步锁，单线程场景下性能远低于 ArrayDeque，官方也早已不推荐使用
单调栈单调性搞反	结果完全错误，找不到正确的边界元素	记牢口诀：找「下一个更大元素」用单调递减栈；找「下一个更小元素」用单调递增栈	我判断单调性的核心逻辑是：遇到目标值时需要弹出栈内不符合条件的元素，栈内剩余元素自然保持对应单调性
边界条件遗漏	栈空弹出抛异常、首尾元素计算不到结果、数组越界	1. 弹出前必须判空；2. 哨兵技巧：数组首尾添加极值元素统一边界；3. 结果数组初始化默认值兜底	我处理边界问题常用哨兵技巧，比如柱状图问题首尾加 0，既避免了栈空判断，又保证首尾柱子都能被正确计算
双栈操作不同步	最小栈等设计题中，最小值与主栈元素不对应，结果错乱	入栈、出栈操作严格同步；优化版需明确弹出条件，值相等时才触发辅助栈弹出	双栈问题最容易踩的坑就是只弹主栈不弹辅助栈，我写的时候会严格保证两个栈的操作成对出现
表达式求值操作数顺序颠倒	减法、除法结果符号或数值完全错误	牢记「先弹出的是右操作数，后弹出的是左操作数」，运算时左操作数在前	后缀表达式是左操作数在前、右操作数在后，入栈顺序先左后右，所以弹出时先拿到的是右操作数，减法除法一定要注意顺序
单调栈存值还是存下标混淆	无法计算元素间隔、矩形宽度等位置相关结果	仅需值比较的场景可存值；涉及位置、距离、宽度计算的场景，一律存下标	我一般默认存下标，因为下标既能拿到值，又能计算位置差，通用性更强，只有纯值匹配的场景才直接存值
相等元素处理不当	单调栈死循环、边界计算错误、结果偏差	明确相等元素的处理逻辑：找严格更大 / 更小时，相等元素直接压栈；找非严格的则弹出	比如每日温度问题，温度相等时不算更高温度，所以相等时直接压栈，保证每个元素的右边界都是严格大于它的第一个元素

步骤	当前符号	栈状态 (底→顶)	操作说明
1	2	[2]	数字，压栈
2	1	[2,1]	数字，压栈
3	+	[3]	弹 2 和 1，2+1=3 压回
4	3	[3,3]	数字，压栈
5	*	[9]	弹 3 和 3，3*3=9 压回，结束

难点项	易踩坑描述	解决方案 & 技巧
Java 栈实现选择	面试时仍使用 `Stack` 类，暴露对 JDK 演进不了解	统一回答：使用 `Deque<Integer> stack = new ArrayDeque<>()`，强调去锁、双端灵活性
出栈操作数顺序	减法 / 除法时直接 `stack.pop() - stack.pop()`，导致顺序反了	先用两个变量 `b = pop(), a = pop()` 接收，再做 `a - b / a / b`
空栈访问	弹出或 peek 前忘记判空，导致 `NoSuchElementException`	所有 `pop/peek` 前必须检查 `isEmpty()`；或者在循环中作为条件（如 while 中取 peek）
辅助栈与主栈不同步	最小栈弹出时忘记处理 `minStack`，导致 getMin 值错误	push/pop 必须成对操作，或者采用条件同步（弹出值 == min 时弹出 minStack）
双栈实现队列的复杂度分析	只说 O(1)，说不出均摊依据	明确回答：每个元素只在 out 空时从 in 搬运一次，n 次操作总搬运 n 次，均摊 O(1)
单调栈何时用下标何时用值	不知道存下标能得到距离信息	需要计算“距离”、“间隔”这类信息时，栈内必须存下标，值为单纯的比较条件
边界条件处理	字符串扫描完栈未空（左括号多余），或中途右括号不匹配处理不及时	最终检查 `return stack.isEmpty()`；中途不匹配直接 `return false`
后缀表达式计算忽略负数/多位数	`Integer.parseInt` 能处理，但遇到非数字符号判断分支有遗漏	用 `switch` 明确覆盖 `+ - * /`，`default` 分支做数字解析；注意除法向零截断（Java 默认行为）