面试经典 150 题-栈

LeetCode 面试经典 150 题-栈

有效的括号

栈

  1. 如果是左括号则入栈，如果是右括号则查看栈顶是否匹配。
  2. 最后判断栈是否为空。
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
class Solution {
    public boolean isValid(String s) {
        // 剪枝
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        // 初始化存放左右括号的哈希表
        Map<Character, Character> hash = new HashMap<>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        // 栈
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            // 左括号入栈
            if (!hash.containsKey(c)) {
                stack.push(c);
            } else if (stack.isEmpty() || stack.pop() != hash.get(c)) {
                // 右括号查看是否匹配
                return false;
            }
        }
        // 返回结果
        return stack.isEmpty();
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

简化路径

栈

把 path 用 / 分割，得到一个字符串列表。

遍历字符串列表的同时，用栈维护遍历过的字符串：

  • 如果当前字符串是空串或者 .，什么也不做（跳过）。
  • 如果当前字符串不是 ..，那么把字符串入栈。
  • 否则弹出栈顶字符串（前提是栈不为空），模拟返回上一级目录。
  • 最后把栈中字符串用 / 拼接起来（最前面也要有个 /）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String simplifyPath(String path) {
        // 定义栈
        List<String> stack = new ArrayList<>();
        // 分割字符串并遍历
        for (String s : path.split("/")) {
            // 跳过
            if (s.isEmpty() || s.equals(".")) {
                continue;
            } else if (!s.equals("..")) {
                // 加入栈
                stack.add(s);                
            } else if (!stack.isEmpty()){
                // 回退上一级目录
                stack.remove(stack.size() - 1);
            }
        }

        // 返回结果
        return "/" + String.join("/", stack);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

最小栈

栈

可以使用辅助栈，在入栈的时候将当前栈的最小元素也加入最小栈，这里只分析不使用辅助栈的方法。

栈中存储的是当前元素+当前元素的最小值。

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
class MinStack {

    private Deque<int[]> stack = new ArrayDeque<>();

    public MinStack() {
        // 初始时放入一个哨兵节点
        stack.push(new int[] {0, Integer.MAX_VALUE});
    }
    
    public void push(int val) {
        stack.push(new int[] {val, Math.min(getMin(), val)});
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        return stack.peek()[0];
    }
    
    public int getMin() {
        return stack.peek()[1];
    }
}
  • 时间复杂度：所有操作均为 O(1)。
  • 空间复杂度：O(q)。其中 q 是 push 调用的次数。最坏情况下，只有 push 操作，需要 O(q) 的空间保存元素。

逆波兰表达式求值

栈

遇到数字放入栈，遇到符号弹出两个操作数进行运算，再将结果放入栈中，最后返回栈中的内容。

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
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        // 遍历
        for (String s : tokens) {
            // 是数字入栈
            if (s.matches("^-?\\d+$")) {
                stack.push(Integer.parseInt(s));
            } else {
                int b = stack.pop();
                int a = stack.pop();
                // 是符号运算
                switch (s) {
                    case "+" :
                        stack.push(a + b);
                        break;
                    case "-" :
                        stack.push(a - b);
                        break;
                    case "*" :
                        stack.push(a * b);
                        break;
                    default:
                        stack.push(a / b);
                }
            }
        }
        return stack.peek();
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

基本计算器

括号展开+栈

思路是通过栈来将括号展开，确定将括号展开后的符号。

  1. 初始化：栈 ops 初始化为 [1]，表示默认符号为 +。

  2. 遍历字符串：

    如果是空格，跳过。
    如果是 + 或 -，更新符号 sign。
    如果是 (，将当前符号入栈（进入一个新的运算子区域）。
    如果是 )，弹出栈顶元素，恢复到上一级的符号。
    如果是数字，解析并计算出数字，累加到结果 ret 中。

  3. 返回结果：当遍历完整个字符串后，ret 即为最终计算的结果

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
41
42
43
44
class Solution {
    public int calculate(String s) {
        // 定义符号栈
        Deque<Integer> ops = new ArrayDeque<>();
        ops.push(1);
        // 遍历字符串
        int sign = 1, ans = 0;
        int n = s.length();
        int i = 0;
        while (i < n) {
            // 如果是空格
            if (s.charAt(i) == ' ') {
                i++;
            } else if (s.charAt(i) == '+') {
                // +，更新符号
                sign = ops.peek();
                i++;
            } else if (s.charAt(i) == '-') {
                // -，更新符号
                sign = -ops.peek();
                i++;
            } else if (s.charAt(i) == '(') {
                // 进入到新的计算区域
                ops.push(sign);
                i++;
            } else if (s.charAt(i) == ')') {
                // 回退到上一层的状态
                ops.pop();
                i++;
            } else {
                // 如果是数字
                int num = 0;
                while (i < n && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                // 更新结果
                ans += sign * num;
            }
        }

        return ans;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

进阶

如果还有*、/、%等等符号，可以用双栈。

  1. 初始化哈希表存储运算符及其优先级。
  2. 遍历字符串：
    • 左括号：加入符号栈。
    • 右括号：不断计算当前符号栈和数字栈中的值，直到遇到左括号，把左括号弹出。
    • 数字：取完整的数字加入数字栈。
    • 符号：如果前一个字符是 ( 或运算符（+ 或 -），则需要先在栈中加入一个 0（这代表此处有一个隐式的 0 操作数）。接下来，判断栈中是否有高优先级的操作符，如果有，则执行计算并弹出栈中的操作符。
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
class Solution {
    // 运算符优先级
    Map<Character, Integer> map = new HashMap<>() {{
        put('+', 1);
        put('-', 1);
        put('*', 2);
        put('/', 2);
        put('%', 2);
        put('^', 3);
    }};

    public int calculate(String s) {
        // 去掉空格
        s = s.replaceAll(" ", "");
        char[] str = s.toCharArray();
        int n = str.length;
        // 定义双栈
        Deque<Character> ops = new ArrayDeque<>();
        Deque<Integer> nums = new ArrayDeque<>();
        // 初始时加入0
        nums.push(0);

        // 遍历字符串
        for (int i = 0; i < n; i++) {
            char c = str[i];
            // 左括号
            if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                // 右括号，计算
                while(!ops.isEmpty() && ops.peek() != '(') {
                    cal(ops, nums);
                }
                // 弹出左括号
                ops.pop();
            } else if (Character.isDigit(c)) {
                // 如果是数字，则获取完整的数字
                int num = 0;
                while (i < n && Character.isDigit(str[i])){
                    num = num * 10 + (str[i] - '0');
                    i++;
                }
                nums.push(num);
                i--;    // 外层for循环还要+1
            } else {
                // 如果是符号，且前一个字符是左括号或+-
                if (i > 0 && (str[i-1] == '(' || str[i-1] == '+' || str[i-1] == '-')) {
                    nums.push(0);
                }
                // 判断优先级并计算
                while (!ops.isEmpty() && ops.peek() != '(') {
                    char prev = ops.peek();
                    if (map.get(prev) >= map.get(c)) {
                        cal(ops, nums);
                    } else {
                        break;
                    }
                }
                // 将当前符号入栈
                ops.push(c);
            }
        }

        // 计算栈中剩余内容
        while (!ops.isEmpty() && ops.peek() != '(') {
            cal(ops, nums);
        }
        
        return nums.peek();

    }

    private void cal(Deque<Character> ops, Deque<Integer> nums) {
        // 边界条件
        if (nums.size() < 2 || ops.isEmpty()) return;
        // 计算
        int b = nums.pop();
        int a = nums.pop();
        char op = ops.pop();
        int ans = 0;
        switch (op) {
            case '+' :
                ans = a + b;
                break;
            case '-' :
                ans = a - b;
                break;
            case '*' :
                ans = a * b;
                break;
            case '/' :
                ans = a / b;
                break;
            case '^' :
                ans = (int)Math.pow(a, b);
                break;
            case '%' :
                ans = a % b;
                break;
            default :
        }   

        // 入栈
        nums.push(ans);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

补充

Deque<Integer> stack = new LinkedList<Integer>()和Deque<Integer> stack = new ArrayDeque<Integer>()的区别：

  1. 底层实现

    LinkedList：底层使用双向链表来实现 Deque。每个元素在内存中是一个节点，包含指向前后元素的指针。
    ArrayDeque：底层使用动态数组（类似于 ArrayList）来实现 Deque。数组的大小会根据元素的数量动态调整。

  2. 性能差异

    LinkedList：
    插入和删除操作（在队头和队尾）是常数时间操作，O(1)。
    但是访问元素（例如通过索引）需要遍历链表，时间复杂度是 O(n)。
    ArrayDeque：
    插入和删除操作（在队头和队尾）通常是 O(1)，但如果数组需要扩容（当数组满时），扩容操作是 O(n)。
    访问元素的时间复杂度是 O(1)，因为它使用数组，所以可以直接通过索引访问。

  3. 内存占用

    LinkedList：由于每个元素都需要额外的内存来存储指向前后节点的指针，因此每个元素的内存占用较大。
    ArrayDeque：数组的内存占用通常较小，但当需要扩容时，可能会分配更大的数组，因此可能会浪费一些内存。

  4. 线程安全性

    LinkedList 和 ArrayDeque 都不是线程安全的。如果在多线程环境中需要操作它们，应该使用同步机制（如 synchronized）或使用 ConcurrentLinkedDeque 等线程安全的实现。

  5. 适用场景

    LinkedList：适合频繁插入和删除元素的场景，尤其是在队列的两端进行操作时，性能较好。
    ArrayDeque：适合需要高效随机访问和较少插入删除操作的场景，尤其是在栈或队列的应用中，通常会比 LinkedList 更高效。

总结：

如果你需要频繁地进行插入和删除操作，LinkedList 是一个不错的选择。
如果你更关注性能，尤其是栈或队列操作的效率，ArrayDeque 通常会提供更好的性能。
算法笔记 > 栈
#栈
面试经典 150 题-栈
http://example.com/2025/01/10/posts/hot150-7/
作者
Xuan Yang
发布于
2025年1月10日
许可协议