字符串解码（LeetCode 394）

字符串解码（LeetCode 394）

k[encoded_string] → 将 encoded_string 重复 k 次。

public String decodeString(String s) {
    Deque<Integer> countStack = new ArrayDeque<>();
    Deque<StringBuilder> strStack = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int k = 0;
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            k = k * 10 + (c - '0');
        } else if (c == '[') {
            countStack.push(k); k = 0;
            strStack.push(cur); cur = new StringBuilder();
        } else if (c == ']') {
            int repeat = countStack.pop();
            StringBuilder prev = strStack.pop();
            for (int i = 0; i < repeat; i++) prev.append(cur);
            cur = prev;
        } else {
            cur.append(c);
        }
    }
    return cur.toString();
}

行星碰撞（LeetCode 735）

正数向右，负数向左。只有右行星 & 左行星相遇才碰撞；同向不碰撞。

public int[] asteroidCollision(int[] asteroids) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int a : asteroids) {
        boolean alive = true;
        while (alive && a < 0 && !stack.isEmpty() && stack.peek() > 0) {
            int top = stack.peek();
            if (top < -a) {
                stack.pop();           // 栈顶爆炸，继续检测
            } else if (top == -a) {
                stack.pop(); alive = false;  // 同归于尽
            } else {
                alive = false;               // 当前行星爆炸
            }
        }
        if (alive) stack.push(a);
    }
    int[] result = new int[stack.size()];
    for (int i = result.length - 1; i >= 0; i--) result[i] = stack.pop();
    return result;
}

每日温度（LeetCode 739）进阶变体

找每个位置右边第一个更大的温度，输出等待天数：

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();  // 单调递减，存下标
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            result[idx] = i - idx;
        }
        stack.push(i);
    }
    return result;
}

去除重复字母（LeetCode 316）

去除重复字母，结果字典序最小，且每个字母只出现一次。

public String removeDuplicateLetters(String s) {
    int[] count = new int[26];
    boolean[] used = new boolean[26];
    for (char c : s.toCharArray()) count[c - 'a']++;
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        count[c - 'a']--;
        if (used[c - 'a']) continue;
        // 栈顶比 c 大 且 后面还有栈顶字符 → 弹出
        while (!stack.isEmpty() && stack.peek() > c && count[stack.peek() - 'a'] > 0) {
            used[stack.pop() - 'a'] = false;
        }
        stack.push(c);
        used[c - 'a'] = true;
    }
    StringBuilder sb = new StringBuilder();
    for (char c : stack) sb.append(c);
    return sb.reverse().toString();
}

总结