类	引入版本	设计目的
`Stack`	Java 1.0	基于Vector实现的传统栈
`Deque`	Java 1.6	双端队列，更现代的接口

方面	`Stack`	`Deque` (ArrayDeque)
数据结构	继承自Vector（动态数组）	循环数组
线程安全	是（Vector是同步的）	否
性能	较差（有同步开销）	优秀（无锁）
方法名	`push()`, `pop()`, `peek()`	`push()`, `pop()`, `peek()` 等
功能	只有栈操作	栈 + 队列操作
Java建议	不推荐使用	推荐使用

❓为什么 Stack 被弃用

继承设计不佳

// Stack 继承了 Vector 的所有方法
stack.get(0);      // 可以直接访问任意位置，破坏栈的封装
stack.remove(1);   // 可以直接删除中间元素
stack.add(2, "X"); // 可以直接在中间插入

这不应该是栈的行为！ 栈应该是LIFO的

线程安全开销

// Vector 的所有方法都是同步的
public synchronized E push(E item) {
    addElement(item);
    return item;
}

即使单线程使用也有同步开销

Java 1.6引入Deque，提供了更清晰、更高效的栈实现

在 Stack 类的JavaDoc中明确写着：

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.
Deque接口及其实现提供了一组更完整和一致的后进先出堆栈操作，应该优先使用此类。

只有在如下情况使用 Stack：

遗留代码兼容
需要线程安全的栈（但可以考虑ConcurrentLinkedDeque）

一、有效的括号

20. 有效的括号↗

简单

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = ”()”

输出：true

示例 2：

输入：s = ”()[]{}”

输出：true

示例 3：

输入：s = ”(]”

输出：false

示例 4：

输入：s = ”([])”

输出：true

示例 5：

输入：s = ”([)]”

输出：false

提示：

1 <= s.length <= 10^4
s 仅由括号 '()[]{}' 组成

1.1 逆序遍历

遇到右括号就入栈，遇到左括号就弹栈

class Solution {
    /**
     * 20. 有效的括号（逆序遍历）
     *
     * @param s		提供的数组
     * @return 		是否为有效括号排列
     */
    public boolean isValid(String s) {
        Deque<Character> st = new ArrayDeque<>();
        boolean ans = true;
        
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            switch (c) {
                case ')', ']', '}': 
                    st.push(c);
                    break;
                case '(': 
                    ans = st.size() > 0 && st.pop() == ')';
                    break;
                case '[': 
                    ans = st.size() > 0 && st.pop() == ']';
                    break;
                case '{': ans = st.size() > 0 && st.pop() == '}';
            }
            if (!ans) break;
        }
        
        return ans && st.size() == 0;	// 例如“]”这种纯右括号的字符串，会堆积在栈内
    }
}

执行用时2ms，击败97.67%，复杂度O(N)

消耗内存42.46MB，击败71.37%，复杂度O(N)

1.2 正序遍历

遇见左括号，就把他对应的右括号压进去
遇见右括号，弹出来看看是不是跟自己一样

class Solution {
    /**
     * 20. 有效的括号（正序遍历）
     *
     * @param s		提供的数组
     * @return 		是否为有效括号排列
     */
    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('}');
            else if (stack.isEmpty() || stack.pop() != c) return false;
        }
        
        return stack.isEmpty();
    }
}

执行用时2ms，击败97.67%，复杂度O(N)

消耗内存42.68MB，击败41.25%，复杂度O(N)

二、最小栈

155. 最小栈↗

中等

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

-2^31 <= val <= 2^31 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 10^4 次

2.1 双栈

维护一个正常栈的同时维护一个最小栈
❓会不会出现9、Integer.Min_VALUE、7这种情况，有一个极小值卡在最小栈顶，导致其他可能为第二小的值丢失
不会
9（压入st，mi）👉 -1（压入st，mi） 👉 7（压入st） 👉 6（压入st）
此时发现，想要弹出-1，必须先弹出可能为第二小的7和6

class MinStack {
    /**
     * 155. 最小栈（双栈）
     */
    private Deque<Integer> st;
    private Deque<Integer> mi;

    public MinStack() {
        st = new ArrayDeque<>();
        mi = new ArrayDeque<>();
        mi.push(Integer.MAX_VALUE);
    }

    public void push(int val) {
        st.push(val);
        if (mi.peek() >= val) {
            mi.push(val);
        }
    }

    public void pop() {
        int val = st.pop();
        if (val == mi.peek()) {
            mi.pop();
        }
    }

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

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

执行用时5ms，击败66.03%

消耗内存46.18MB，击败57.48%

2.2 最小前缀值

定义Deque<int[]> st = new ArrayDeque<>();

其中int[]数组存储2个数：当前的值、当前最小值（栈中自己及以下元素的最小值）

因此，在向栈中压入元素时，我们可以得到递推公式

preMin[i]=min(preMin[i−1],\ nums[i])

class MinStack {
    /**
     * 155. 最小栈（最小前缀值）
     */
    private Deque<int[]> st = new ArrayDeque<>();

    public MinStack() {
        // 题中说明测试用例保证栈非空
        st.push(new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE});
    }
    
    public void push(int val) {
        st.push(new int[]{val, Math.min(val, getMin())});
    }
    
    public void pop() {
        st.pop();
    }
    
    public int top() {
        return st.peek()[0];
    }
    
    public int getMin() {
        return st.peek()[1];
    }
}

执行用时4ms，击败99.46%

消耗内存46.50MB，击败9.01%

三、字符串解码

394. 字符串解码↗

中等

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 10^5。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

1 <= s.length <= 30
s 由小写英文字母、数字和方括号 '[]' 组成
s 保证是一个有效的输入。
s 中所有整数的取值范围为 [1, 300]

3.1 逆序遍历

以3[a2[c]]为示例，遇到非数字直接压入栈，遇到数字（先解析这个数字，因为可能不是一位数）不断弹栈

st:		<= 栈顶
	[
	c
	]
	]	<= 栈底

依次弹出[c]，解析得到重复数字2次，得到cc，再压回栈中（以适应嵌套关系）

st:		<= 栈顶
	[
	a
	cc
	]	<= 栈底

此处同理，最后不断弹出栈中元素并拼接成结果即可

class Solution {
    /**
     * 394. 字符串解码（逆序遍历）
     *
     * @param s		待解码字符串
     * @return 		解码后的字符串
     */
    public String decodeString(String s) {
        Deque<String> st = new ArrayDeque<>();
        
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            
            if (Character.isDigit(c)) {          
                // 获得重复次数
                int num = 0;
                int base = 1;
                while (i >= 0 && Character.isDigit(s.charAt(i))) {
                    num = (s.charAt(i) - '0') * base + num;
                    base *= 10;
                    i--;
                }
                
                st.pop(); // 弹出 '['
                
                StringBuilder sb = new StringBuilder();
                while (!st.peek().equals("]")) {
                    sb.append(st.pop());
                }
                st.pop(); // 弹出 ']'
                
                // 重复字符串并压栈
                String repeated = sb.toString().repeat(num);
                st.push(repeated);
                i++;	// 最后一次 while 多减了一次
            } else {
                // 遇到括号或字母，直接入栈
                st.push(String.valueOf(c));
            }
        }
        
        // 拼接结果
        StringBuilder ans = new StringBuilder();
        while (!st.isEmpty()) {
            ans.append(st.pop());
        }
        return ans.toString();
    }
}

执行用时1ms，击败86.02%，复杂度O(N)

消耗内存42.23MB，击败42.32%，复杂度O(N)

四、每日温度

739. 每日温度↗

中等

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100

4.1 单调栈（递减）

要计算的内容涉及到上一个或者下一个更大或者更小的元素，考虑单调栈

新元素入栈前，弹出栈顶所有比他小的元素即可，表示找到了下一个更高的温度

由于每个元素只会入栈一次，所以可以直接修改temperatures数组，而无需额外的空间开销

class Solution {
    /**
     * 739. 每日温度（单调栈）
     *
     * @param temperatures 	柱子高度数组
     * @return 				每天下一个更高温度出现在几天后 
     */
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> st = new ArrayDeque<>();

        for (int i = 0; i < temperatures.length; i++) {
            while (st.size() > 0 && temperatures[i] > temperatures[st.peek()]) {
                int l = st.pop();
                temperatures[l] = i - l;
            }
            st.push(i);
        }

        while (st.size() > 0) temperatures[st.pop()] = 0;	// 弹出剩余元素
        
        return temperatures;       
    }
}

五、柱状图中最大的矩形

84. 柱状图中最大的矩形↗

困难

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

1 <= heights.length <=10^5
0 <= heights[i] <= 10^4

5.1 单调栈（递增）

要计算的内容涉及到上一个或者下一个更大或者更小的元素，考虑单调栈
单调栈即栈顶到栈底的元素都是单调递增 / 单调递减的
新入栈的元素在入栈前弹出栈顶所有比他大（或小，具体看单调递增还是递减）的元素
直观来看，存储了一个阶梯状的物体

对于递增栈，由于弹出操作，实际上只有两种情况

...23456 1...，单增后突然断崖下降
...6543210...，单调递减

想象从这个矩形数组中抽取连续的几个矩形出来当成一个装水的容器，往这个容器中注水，水恰好碰到最矮的那个矩形顶部时，就是矩形的最大面积

class Solution {
    /**
     * 84. 柱状图中最大的矩形
     *
     * @param heights	高度数组
     * @return 			最大矩形面积
     */
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> st = new ArrayDeque<>();
        int ans = 0;
        int length = heights.length;
        
        for (int i = 0; i <= length; i++) {
            // 哨兵，处理循环结束后，栈中剩余的递增数据
            int h = (i == length) ? 0 : heights[i];
            
            // 弹出所有比新插入元素大的数，栈中期望存储的是23456这种阶梯递增数据
            while (st.size() > 0 && h < heights[st.peek()]) {
                int height = heights[st.pop()];
                // 对于6543这种递减压入栈的，压入5前弹出6，栈为空，宽取i
                // 因为如果栈为空，说明先前把所有元素弹出了
                // 而被弹出的元素肯定比5要大，所以5可以放心当高
                // 如果是06543，压入5弹出6，栈底有0标识着宽的起点
                int width = st.size() > 0 ? i - st.peek() - 1 : i;
                ans = Math.max(ans, height * width);
            }
            
            st.push(i);
        }
        
        return ans;
    }
}

Thanks for reading!

力扣hot100-《栈》章节题解

周一 1月 26 2026 栈

2853 字 · 17 分钟

algorithm leetcode hot100 stack

Yiiyye's Blog

欲买桂花同载酒，终不似，少年游！

力扣hot100-《栈》章节题解

一、有效的括号

1.1 逆序遍历

1.2 正序遍历

二、最小栈

2.1 双栈

2.2 最小前缀值

三、字符串解码

3.1 逆序遍历

四、每日温度

4.1 单调栈（递减）

五、柱状图中最大的矩形

5.1 单调栈（递增）

力扣hot100-《栈》章节题解