Plantre
plantre
2025-06-11
目录

辅助栈

# 155. 最小栈 - 力扣（LeetCode） (opens new window)

class MinStack {
        Deque<Integer> stack;
        Deque<Integer> minStack;
    public MinStack() {
        stack=new LinkedList<Integer>();
        minStack=new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        stack.push(val);
        minStack.push(Math.min(minStack.peek(),val));
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 20. 有效的括号 - 力扣（LeetCode） (opens new window)

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if ( n % 2 == 1 ) return false;
        Map<Character, Character> pairs = new HashMap<Character, Character>(){
            {
                put(')', '(');
                put(']', '[');
                put('}', '{');
            }
        };
        Deque<Character> stack = new LinkedList<Character>();
        for(int i=0; i < n;i++){
            char ch = s.charAt(i);
            // 右括号
            if(pairs.containsKey(ch)){
                if(stack.isEmpty() || stack.peek() != pairs.get(ch)) return false;
                stack.pop();
                // 左括号
            }else{
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 32. 最长有效括号 - 力扣（LeetCode） (opens new window)

栈

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        // 重点在这里, -1是唯一能同时处理 ​​字符串起始位置​​、​​右括号开头​​、​​连续有效子串​​ 三种边界情况的初始值
        // 将有效长度的计算统一为 当前索引 - 栈顶索引​​，无需额外分支判断
        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()) {
                    //栈中始终存储​​最后一个无效右括号的索引​​（或初始 -1）
                    stack.push(i); // 更新起点
                } else {
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

双指针

// t
1

# 224. 基本计算器 - 力扣（LeetCode） (opens new window)

class Solution {
    public int calculate(String s) {
        int res = 0;
        int num = 0;
        int sign = 1;
        Stack<Integer> stack = new Stack();
        char[] chars = s.toCharArray();
        int len = chars.length;
        for(int i = 0; i < len; i++){
            char c = chars[i];
            if (c == ' ') continue;
            // 如果当前字符是一个数字，则用num进行记录
            if (c >= '0' && c <= '9'){
                num = num * 10 + c - '0';
                // 判断当前数字是否已经取完
                if(i < len - 1 && '0' <= chars[i+1] && chars[i+1] <= '9'){
                    continue;
                }
            } else if (c == '+' || c == '-'){
                // 将num置为0，用来存放当前符号(+/-)之后的数字
                num = 0;
                sign = c=='+' ? 1:-1;
            } else if (c == '('){
                stack.push(res);
                stack.push(sign);
                res = 0;
                sign = 1; 
            } else if (c == ')'){
                //  '('前边的符号出栈
                sign = stack.pop();
                //   将num替换为括号中的计算结果
                num = res;
                //   将res替换为括号前边的计算结果
                res = stack.pop();
            }
            res += sign * num;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 227. 基本计算器 II - 力扣（LeetCode） (opens new window)

# 📊 核心区别总览

对比维度 224题（基本计算器） 227题（基本计算器 II）
支持的运算符 仅加减法（+, -）和括号 加减乘除（+, -, *, /），无括号
括号处理 ✅ 需处理嵌套括号，用栈保存当前符号状态 ❌ 不支持括号
优先级处理 无优先级（仅加减），括号决定计算顺序 需处理乘除优先于加减，用栈延迟计算加减法
解题核心思路 符号栈 + 实时计算 数值栈 + 乘除立即计算
空间复杂度 O(n)（栈深与括号嵌套层数相关） O(n)（栈存储中间结果）
class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new LinkedList<>();
        char preSign = '+';
        int num = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            // 处理连续数字
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }
            // 遇到运算符或末尾时处理前一个运算符
            if (!Character.isDigit(c) && c != ' ' || i == n - 1) {
                switch(preSign) {
                    case '+': stack.push(num); break;
                    case '-': stack.push(-num); break;
                    case '*': stack.push(stack.pop() * num); break;
                    case '/': stack.push(stack.pop() / num); break;
                }
                // 更新前一个运算符
                preSign = c;
                num = 0;
            }
        }
        int res = 0;
        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 394. 字符串解码 - 力扣（LeetCode） (opens new window)

class Solution {
    public String decodeString(String s) {
        // 存储重复次数（如遇到 [ 前累积的数字）
        Deque<Integer> numStack = new ArrayDeque<>();
        // 存储当前括号外的部分结果
        Deque<StringBuilder> strStack = new ArrayDeque<>();
        // 动态记录当前层字符串
        StringBuilder currStr = new StringBuilder();
        // 动态累积数字（处理多位数）
        int num = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '[') {
                numStack.push(num);
                strStack.push(currStr);
                num = 0;
                currStr = new StringBuilder();
            } else if (c == ']') {
                int repeat = numStack.pop();
                StringBuilder prevStr = strStack.pop();
                StringBuilder temp = new StringBuilder();
                for (int i = 0; i < repeat; i++) {
                    // 注意这里是currStr而不是prevStr
                    temp.append(currStr);
                }
                currStr = prevStr.append(temp);
            } else {
                currStr.append(c);
            }
        }
        return currStr.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

dfs

class Solution {
    public String decodeString(String s) {
        // 当前索引 index（需传递引用或数组模拟指针）
        int[] index = new int[]{0};
        return dfs(s, index);
    }

    private String dfs(String s, int[] index) {
        StringBuilder res = new StringBuilder();
        int num  = 0;
        while (index[0] < s.length()) {
            char c = s.charAt(index[0]);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
                index[0]++;
            } else if (c == '[') {
                index[0]++;
                // 递归处理内层
                String inner = dfs(s, index);
                while (num > 0) {
                    num--;
                    res.append(inner);
                }
            } else if (c == ']') {
                index[0]++;
                return res.toString(); 
            } else {
                res.append(c);
                index[0]++;
            }
        }
        return res.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 946. 验证栈序列 - 力扣（LeetCode） (opens new window)

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num : pushed){
            stack.push(num);
            while(!stack.isEmpty() && stack.peek() == popped[i]){
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 232. 用栈实现队列 - 力扣（LeetCode） (opens new window)

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue() {
        inStack = new LinkedList<Integer>();
        outStack = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        if(outStack.isEmpty()){
            while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }
    
    public int peek() {
        if(outStack.isEmpty()){
            while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# 单调栈

# 739. 每日温度 - 力扣（LeetCode） (opens new window)

示例

输入: T= [73,74,75,71,69,72,76,73]

我们从后往前遍历：

stack=[]

7（73）. 栈没有元素，返回0，加入自己的下标

stack=[7] 堆栈=[7]

6（76）. 弹出所有比自己小的元素，T[7]

stack=[6] 堆栈=[6]

5（72）. 没有比自己小的元素，返回 栈顶（6）-当前下标=1 ，加入自己的下标

stack=[6,5] 堆栈=[6,5]

4（69）. 没有比自己小的元素，返回 栈顶（5）-当前下标=1 ，加入自己的下标

stack=[6,5,4] 堆栈=[6,5,4]

3（71）. 栈顶4对应的69比我小，弹出！返回 栈顶（5）-当前下标=2 ，加入自己的下标

stack=[6,5,3] 堆栈=[6,5,3]

2（75）. 栈3和5对应的71和72比我小，弹出！返回 栈顶（6）-当前下标=4 ，加入自己的下标

stack=[6,2] 堆栈=[6,2]

1（74）. 没有比自己小的元素，返回 栈顶（2）-当前下标=1 ，加入自己的下标

stack=[6,2,1] 堆栈=[6,2,1]

0（73）. 没有比自己小的元素，返回 栈顶（1）-当前下标=1 ，加入自己的下标

stack=[6,2,1,0] 堆栈=[6,2,1,0]

所以我们就得到输出 answer = [1,1,4,2,1,1,0,0]

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] ans=new int[temperatures.length];
        //存储下标
        Stack<Integer> st = new Stack<>();
        //从后往前遍历
        for(int i = temperatures.length - 1;i >= 0; i--){
            //自顶向下弹出所有比当前温度小的
            while(!st.isEmpty() && temperatures[i] >= temperatures[st.peek()]){
                st.pop();
            }
            //如果栈空了说明后面没有比自己大的，答案是0;否则是栈顶下标和自己下标的差
            ans[i] = st.isEmpty() ? 0 : st.peek() - i;
            //加入当前温度下标
            st.push(i);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 402. 移掉 K 位数字 - 力扣（LeetCode） (opens new window)

可能你会问：什么时候用单调栈？

需要给当前的元素，找右边/左边第一个比它大/小的位置。

记住这两句话：

单调递增栈，利用波谷剔除栈中的波峰，留下波谷；

单调递减栈，利用波峰剔除栈中的波谷，留下波峰。

本题想维护高位递增，即，元素想找右边第一个比它小的数，即右侧第一个波谷。

单调递增栈遇到波谷，用它来剔除栈中的波峰，维持单增。

留下波谷保持了单增，而剔除掉的栈中字符，就是删掉的字符。

class Solution {
    public String removeKdigits(String num, int k) {
        Deque<Character> stack = new ArrayDeque<>(num.length());
        for (char c: num.toCharArray()) {
            // 只要k>0且当前的c比栈顶的小，则栈顶出栈，k--
            while (k > 0 && !stack.isEmpty() && c < stack.peek()) {
                stack.pop();
                k--;
            }
            // 当前的字符不是"0"，或栈非空（避免0入空栈），入栈
            if (c!='0' || !stack.isEmpty()) {
                stack.push(c);
            }
        }
        //// 如果还没删够，要从stack继续删，直到k=0
        while (k > 0 && !stack.isEmpty()) {
            stack.pop();
            k--;
        }
        StringBuffer buffer = new StringBuffer();
        while (!stack.isEmpty()) {
            buffer.append(stack.pollLast());
        }
        return buffer.length() == 0 ? "0" : buffer.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
编辑 (opens new window)
上次更新: 2025/07/25, 12:08:10
滑动窗口
贪心

← 贪心→

最近更新
01
加油鸭
07-30
02
要点总结
07-28
03
字符串
07-15
更多文章>
Theme by Vdoing | Copyright © 2025-2025 plantre | MIT License