LeetCode 热题 100-栈

有效的括号

栈

遇到左括号就放入栈，遇到右括号就开始匹配。最后如果栈不为空，就说明匹配失败，否则成功。

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};

        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (!pairs.containsKey(c)) {    // 左括号就入栈
                stack.push(c);
            }  else if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
                return false;
            }
        }

        return stack.isEmpty();
    }
}

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

最小栈

辅助栈

1. 主栈 stack：存储所有元素。
2. 辅助栈 minStk：存储当前栈的最小值。
   • 每次 push 时，将新元素与当前最小值比较，更新 minStk。
   • 每次 pop 时，同时更新主栈和辅助栈，保证 minStk 栈顶始终是当前栈的最小值。

class MinStack {
    Deque<Integer> stack;
    Deque<Integer> minStk;
    public MinStack() {
        stack = new ArrayDeque<>();
        minStk = new ArrayDeque<>();
        minStk.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        stack.push(val);
        minStk.push(Math.min(minStk.peek(), val));
    }
    
    public void pop() {
        stack.pop();
        minStk.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStk.peek();
    }
}

• 时间复杂度：所有操作均为 O(1)。
• 空间复杂度：O(q)。其中 q 是 push 调用的次数。

不使用辅助栈

在主栈中存储每个元素时，同时存储它入栈时的最小值。这样每次入栈时，当前最小值都与数据元素绑定在一起，不需要额外的辅助栈。

1. 每次入栈时：
   • 将新元素与当前栈的最小值（即栈顶的最小值）比较，记录较小的那个作为当前元素的“入栈最小值”。
   • 将数据和当前最小值打包成一对存入栈中。
2. 每次出栈时：
   • 只需弹出栈顶，弹出的同时也会移除与该数据绑定的最小值。
3. 查询最小值：
   • 栈顶的“入栈最小值”即为当前栈中所有元素的最小值。

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 调用的次数。

字符串解码

辅助栈

1. 构建辅助栈 stack， 遍历字符串 s 中每个字符 c:
   • 当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；
   • 当 c 为字母时，在 res 尾部添加 c；
   • 当 c 为 [ 时，将当前 multi 和 res 入栈，并分别置空置 0：
     • 记录此 [ 前的临时结果 res 至栈，用于发现对应 ] 后的拼接操作；
     • 记录此 [ 前的倍数 multi 至栈，用于发现对应 ] 后，获取 multi × […] 字符串。
     • 进入到新 [ 后，res 和 multi 重新记录。
   • 当 c 为 ] 时，stack 出栈，拼接字符串 res = last_res + cur_multi * res，其中:
     • last_res是上个 [ 到当前 [ 的字符串，例如 “3[a2[c]]” 中的 a；
     • cur_multi是当前 [ 到 ] 内字符串的重复倍数，例如 “3[a2[c]]” 中的 2。
2. 返回字符串res。

class Solution {
    public String decodeString(String s) {
        Deque<Integer> numStack = new ArrayDeque<>();
        Deque<String> strStack = new ArrayDeque<>();

        StringBuilder res = new StringBuilder();
        int muiti = 0;
        // 遍历字符串
        for (Character c : s.toCharArray()) {
            // 如果是左括号
            if (c == '[') {
                // 把字符串和数字加入栈
                numStack.push(muiti);
                strStack.push(res.toString());
                // 清空
                muiti = 0;
                res = new StringBuilder();
            } 
            // 如果是右括号
            else if (c == ']') {
                // 拼接字符串
                StringBuilder tmp = new StringBuilder();
                int cur = numStack.pop();
                for (int i = 0; i < cur; i++) {
                    tmp.append(res);
                }
                res = new StringBuilder(strStack.pop() + tmp);
            }
            // 如果是数字
            else if (c >= '0' && c <= '9') {
                muiti = muiti * 10 + Integer.parseInt(c + "");
            }
            // 如果是普通字符
            else {
                res.append(c);
            }
        }

        return res.toString();
    }
}

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

递归

总体思路与辅助栈法一致，不同点在于将 [ 和 ] 分别作为递归的开启与终止条件：

• 当 s[i] == ‘]’ 时，返回当前括号内记录的 res 字符串与 ] 的索引 i （更新上层递归指针位置）；
• 当 s[i] == ‘[‘ 时，开启新一层递归，记录此 […] 内字符串 tmp 和递归后的最新索引 i，并执行 res + multi * tmp 拼接字符串。
• 遍历完毕后返回 res。

1. 递归函数 dfs(s, index):

• index 表示当前正在处理的位置。
• 通过 StringBuilder res 存储当前解码的结果。
• multi 是一个临时变量，用来存储重复的次数。由于重复次数可能是多位数，所以每遇到一个数字就累加到 multi 上。

2. 遍历字符串:

   • 左括号 [: 如果遇到左括号，说明接下来是一个子字符串，需要递归解码括号内的部分。

     • 递归调用 dfs(s, index + 1) 处理括号内部的内容，并更新 index 到递归调用返回的右括号位置。
     • tmp[1] 是括号内的解码结果，multi 是重复次数，把括号内的内容根据 multi 重复添加到结果中。

   • 右括号 ]: 如果遇到右括号，说明当前的括号已经处理完，返回当前解码结果（包含当前部分的字符串以及更新后的 index）。

   • 数字字符: 如果是数字字符（0-9），则通过累加构建完整的重复次数 multi，因为重复次数可能是多位数（如 “10[a]” 表示重复10次）。

   • 普通字符: 普通字符直接追加到结果中。

class Solution {
    public String decodeString(String s) {
        return dfs(s, 0)[0];
    }

    private String[] dfs(String s, int index) {
        StringBuilder res = new StringBuilder();
        int multi = 0;
        // 遍历字符串
        while (index < s.length()) {
            Character c = s.charAt(index);
            // 如果是左括号
            if (c == '[') {
                String[] tmp = dfs(s, index + 1);
                index = Integer.parseInt(tmp[0]);
                while (multi > 0) {
                    res.append(tmp[1]);
                    multi--;
                }
            }
            // 如果是右括号
            else if (c == ']') {
                return new String[] {String.valueOf(index), res.toString()};
            }
            // 如果是数字
            else if (c >= '0' && c <= '9') {
                multi = multi * 10 + Integer.parseInt(String.valueOf(c));
            }
            // 如果是普通字符
            else {
                res.append(String.valueOf(c));
            }
            index++;
        }
        return new String[] {res.toString()};
    }
}

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

每日温度

单调栈

从左向右遍历元素，如果当前元素比栈顶小，直接入栈，等待出现更大元素；否则，把所有小于等于它的元素弹出，并且可以更新每一个弹出的元素的结果，即i - stk.top()，再将当前元素放入。

class Solution {
    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()]) {
                ans[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }

        return ans;
    }
}

• 时间复杂度：O(n)，每个元素最多入栈和出栈一次。
• 空间复杂度：O(n)

从右往左

如果当前元素比栈顶小，直接入栈，并且当前元素的下一个更高温度就是1；否则，把所有小于等于它的元素弹出，再将其放入，当前元素的下一个更高温度就是栈顶元素。即，找到第一个大于当前元素的栈中元素，其值应该是栈顶元素下标-当前元素下标。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        // 遍历数组
        for (int i = n-1; i >= 0; i--) {
            // 找到第一个大于当前元素的栈中元素，注意等于的时候无法更新
            while(!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {
                stack.pop();
            }
            // 栈顶元素下标-当前元素下标
            if (!stack.isEmpty()) {
                ans[i] = stack.peek() - i;
            }
            stack.push(i);
        }

        return ans;
    }
}

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

柱状图中最大的矩形

单调栈

• 在 i 左侧的小于 h 的最近元素的下标 left，如果不存在则为 −1。求出了 left，那么 left+1 就是在 i 左侧的大于等于 h 的最近元素的下标。
• 在 i 右侧的小于 h 的最近元素的下标 right，如果不存在则为 n。求出了 right，那么 right−1 就是在 i 右侧的大于等于 h 的最近元素的下标。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        // 从左往右找到每个下标左边第一个小于等于当前高度的下标
        int[] left = new int[n];
        Arrays.fill(left, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while(!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                left[i] = stack.peek();
            }
            stack.push(i);
        }
        // 从右往左找到每个下标右边第一个小于等于当前高度的下标
        int[] right = new int[n];
        Arrays.fill(right, n);
        stack = new ArrayDeque<>();
        for (int i = n-1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                right[i] = stack.peek();
            }
            stack.push(i);
        }

        // 计算
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}

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

总结

java中栈可以使用Deque<> stk = new ArrayDuque<>();，常用的操作有：

• peek()
• pop()
• push()
• isEmpty()

单调栈的部分需要再好好想想，多练习几道题。