栈

---

20. 有效的括号

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else if (stack.isEmpty()) {
                return false;
            } else if (ch == ')' && stack.pop() != '(') {
                return false;
            } else if (ch == '}' && stack.pop() != '{') {
                return false;
            } else if (ch == ']' && stack.pop() != '[') {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

155. 最小栈

class MinStack {
    private Deque<Integer> stk1 = new ArrayDeque<>();
    private Deque<Integer> stk2 = new ArrayDeque<>();

    public MinStack() {

    }

    public void push(int val) {
        stk1.push(val);
        if (stk2.isEmpty() || val < stk2.peek()) {
            stk2.push(val);
        } else {
            stk2.push(stk2.peek());
        }
    }

    public void pop() {
        stk1.pop();
        stk2.pop();
    }

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

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

394. 字符串解码

// 有些麻烦，栈要入队出队，数字和字符分开存放
class Solution {
    public String decodeString(String s) {
        Deque<Integer> stkNumber = new ArrayDeque<>();
        Deque<Character> stkChar = new ArrayDeque<>();

        int num = 0;
        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                num = num * 10 + ch - '0';
            } else if (ch == ']') {
                // 出栈
                StringBuilder ss = new StringBuilder();
                while (stkChar.peek() != '[') {
                    ss.append(stkChar.pop());
                }
                stkChar.pop();
                int number = stkNumber.pop();
                for (int i = 0; i < number; i++) {
                    for (int j = ss.length() - 1; j >= 0; j--) {
                        stkChar.push(ss.charAt(j));
                    }
                }
            } else {
                if (ch == '[') {
                    stkNumber.push(num);
                    num = 0;
                }
                stkChar.push(ch);
            }
        }
        char[] ans = new char[stkChar.size()];
        for (int i = ans.length - 1; i >= 0; i--) {
            ans[i] = stkChar.pop();
        }

        return new String(ans);
    }
}

739. 每日温度

// 从后往前，单调栈
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] ans = new int[temperatures.length];
        // 单调栈记录下标即可，可以获取温度和计算结果
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = temperatures.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {
                stack.pop();
            }
            ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            // 由于数组默认赋值为0，所以下面这句也行
            // if(!stack.isEmpty()) ans[i] = stack.peek() - i;
            stack.push(i);
        }
        return ans;
    }
}