＜03.08＞Leetcode

class Solution {
    public boolean isValid(String s) {
        if(s.isEmpty())return true;
        Stack<Character> stk = new Stack<Character>();
        for(char c:s.toCharArray()){
            if(c=='(')stk.push(')');
            else if(c=='{')stk.push('}');
            else if(c=='[')stk.push(']');
            else if(stk.isEmpty()||c!=stk.pop())return false;
        }
        return stk.isEmpty();
    }
}

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> min_stack;
    public MinStack() {
        stack = new Stack<>();
        min_stack = new Stack<>();
    }
    public void push(int x) {
        stack.push(x);
        if(min_stack.isEmpty() || x <= min_stack.peek())
            min_stack.push(x);
    }
    public void pop() {
        if(stack.pop().equals(min_stack.peek()))
            min_stack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return min_stack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int multi = 0;
        LinkedList<Integer> stack_multi = new LinkedList<>();
        LinkedList<String> stack_res = new LinkedList<>();
        for(Character c : s.toCharArray()) {
            if(c == '[') {
                stack_multi.addLast(multi);
                stack_res.addLast(res.toString());
                multi = 0;
                res = new StringBuilder();
            }
            else if(c == ']') {
                StringBuilder tmp = new StringBuilder();
                int cur_multi = stack_multi.removeLast();
                for(int i = 0; i < cur_multi; i++) tmp.append(res);
                res = new StringBuilder(stack_res.removeLast() + tmp);
            }
            else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");
            else res.append(c);
        }
        return res.toString();
    }
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stk = new Stack<>();
        int len = temperatures.length;
        int[] result = new int[len];
        for(int i=0;i<len;i++){//对于每一天
            while(!stk.isEmpty()&&temperatures[i]>temperatures[stk.peek()]){
                int pre = stk.pop();
                result[pre] = i - pre;
            }
            stk.add(i);//加入的是index 也是天数
        }
        return result;
    }
}

class Solution {
    public int rob(int[] nums) {
        // dp[i]表示偷盗前i个房屋能拿到的最高金额
        int[] dp = new int[nums.length + 1];
        dp[0] = 0; // 没有房屋时，能偷到的金额为0
        dp[1] = nums[0]; // 只有一个房屋时，能偷到的金额为第一个房屋的金额

        for (int i = 1; i < nums.length; i++) {
            // 对于第i个房屋，可以选择偷或者不偷：
            // 如果偷，则不能偷第i-1个房屋，所以总金额为dp[i-2] + nums[i]
            // 如果不偷，则总金额为dp[i-1]
            dp[i + 1] = Math.max(dp[i - 1] + nums[i], dp[i]);
        }
        return dp[nums.length]; // 返回偷盗所有房屋能拿到的最高金额
    }
}