day11|150，239，347

150

其实不难，理解规律，遇到符号就需要提出来做运算。

class Solution {
    public int evalRPN(String[] tokens) {
        //向零截断，正数向下取整，负数向上取整
        //Queue<Integer> num = new Queue<>()；是错的注意区别
        Deque<Integer> num = new LinkedList<>();//名称用stack更好
        int len = tokens.length;
        //for(String s： tokens)更好
        for(int i = 0; i < len; i++){
            //不能使用==判断字符串是否相等
            if("*".equals(tokens[i])){
                int num1 = num.pop();
                int num2 = num.pop();
                num.push(num1 * num2);
            }else if("/".equals(tokens[i])){
                int num1 = num.pop();
                int num2 = num.pop();
                num.push(num2 / num1);
            }else if(tokens[i].equals("-")){
                int num1 = num.pop();
                int num2 = num.pop();
                num.push(num2 - num1);
            }else if(tokens[i].equals("+")){
                int num1 = num.pop();
                int num2 = num.pop();
                num.push(num2 + num1);
            }else{
                //用valueOf=也可以
                num.push(Integer.parseInt(tokens[i]));
            }
        }
        return num.pop();
    }
}

补充1：java中除法取整

在Java中，整数除法的结果是向下取整的。这意味着当两个整数相除时，结果会舍弃小数部分，只保留整数部分。

符合题目中说的从零取整。

239

感觉不太难，试做一下。

有点难，当最大值失效时，下一个最大值是多少呢。

好难，学习一下。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //这个题目的问题在于，在左移的时候最大值能否保留，如何找到次大值
        //单调队列
        Deque<Integer> deque = new LinkedList<>();
        int n = nums.length;
        
        int[] res = new int[n - k + 1];
        for(int i = 0; i < n; i++){
            //先删前再删后
            while(!deque.isEmpty() && deque.peek() < i - k + 1){
                deque.poll();//头部弹出
            }

            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
                deque.pollLast();//找到最大值
            }

            deque.offer(i);

            if(i >= k - 1){
                res[i - k + 1] = nums[deque.peek()];
            }
        }
        return res;
    }
}

补充1：单调队列

维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。

理解体内的单调队列具体存的什么值，它不是数组，存的仅仅是当前这个i的最大值。

详细来说在这个队列中每次加入的新值，是，以这个下标i为起头，在不知道后面的情况下的可能是最大值的下标，但i现在不一定是起头，所以只是存储起来。

补充2：思路

为了维护当前区间的最大值，所以需要进行比较，确保队列中的数据是在区间内的，所以有第一个循环函数。

第二个函数，则是在新加入值后，以这个下标i为结尾的k可能的最大值，那现在在队列中比我小的值就需要删掉了。这就是第二个循环函数的作用。

两个函数的作用下，最后留在队头的就是我们的答案。

补充3：双端队列的函数

这里右边是头，左边是尾

poll(), peek(), offer()

pollLast(), peekLast()

347

想法是用最大堆维护就好了。

先遍历一遍所有数据统计出现次数，然后再加入最大堆取前k个。

思路没问题，主要语法不熟，多复习!

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequence = new HashMap<>();
        for(int num: nums){
            //写法！ 错的frequence.push(num, frequence.getBy(num) ++);
           
            frequence.put(num, frequence.getOrDefault(num, 0) + 1);
        }

        //为什么是数组？
        //最大根，重要，难写！
        PriorityQueue<int[]> pri = new PriorityQueue<>((pair1, pair2) -> {
            return pair2[1] - pair1[1];
        });

        //注意遍历写法 错for(Map<Integer, Integer> map : frequence)
        for(Map.Entry<Integer, Integer> map : frequence.entrySet()){
            //哪些用add哪些用Put
            //堆怎么add,哪些参数,怎么获得
            pri.add(new int[]{map.getKey(), map.getValue()});
        }

        int[] ans = new int[k];
        for(int i = 0; i < k ; i++){
            哪些用pop哪些用poll
            int[] pair = pri.poll();
            ans[i] = pair[0];
        }

        return ans;
    }
}