代码随想录算法训练营Day10 | 239.滑动窗口的最大值、347.前K个高频元素

LeetCode 239 滑动窗口的最大值

本题思路: 采用单调队列来完成，单调队列就是队列里的元素顺序，是单调递减/递增的情况。
那么我们应该如何维护这个单调队列呢，此处既然是最大值，那么采用的是单调递减的队列。让队列的出口处是当前窗口的最大值。
首先我们需要自己设计一个单调队列，有三个方法

• push()：进队列

  • 进入队列的之前要先将队列中比小的元素全部移除（队列不为空的情况下），然后再进入队列。此时队头元素一定就是最大值

• pop()：出队列

  • 出队列的意思其实就是前三个K已经获得最大值了，那么窗口应该往右移动，需要移除1，然后将 -3 加入到队列。
  • 所以我们在出队列的时候，要判断此时队头元素 是不是我们要移除的 1 ，如果是就移除，不是就不作任何处理。

• getMax()：获取当前窗口内的元素最大值，此时最大值就栈顶元素

class Solution {


        static class MyDeque{
        Deque<Integer> deque = new LinkedList<>();

        // 进队列操作
        void push(int val){
            // 进队列之前，移除从队尾开始的元素，每一个和即将入队的元素进行比较，如果比他小的，都移除
            while (!deque.isEmpty() && val > deque.getLast()){
                deque.pollLast();
            }
            deque.add(val);
        }

        // 出队列操作
        void pop(int val){
            // 就是缩减一个当前窗口的最左边的元素，因为已经判断过了，要往后移动
            // 如果队头元素等于窗口最左边的元素就移除，不等于，不做操作
            if(!deque.isEmpty() && deque.getFirst() == val){
                deque.pollFirst();
            }
        }

        int getMax(){
            return deque.peekFirst();
        }

    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length - k + 1;
        //存放结果元素的数组
        int[] res = new int[len];
        int num = 0;
        //自定义队列
        MyDeque deque = new MyDeque();
        //先将前k的元素放入队列
        for (int i = 0; i < k; i++) {
            deque.push(nums[i]);
        }
        res[num++] = deque.getMax();
        for (int i = k; i < nums.length; i++) {
            //滑动窗口移除最前面的元素，移除是判断该元素是否放入队列
            deque.pop(nums[i - k]);
            //滑动窗口加入最后面的元素
            deque.push(nums[i]);
            //记录对应的最大值
            res[num++] = deque.getMax();
        }
        return res;
    }
}

LeetCode 347 前K个高频元素

本题思路：使用小顶堆，需要实现 PriorityQueue 中的 Comparator接口，并重新写 compare 方法，让它进行元素出现次数对比。
前 K 个高频元素：用小根堆
前 K 个低频元素：用大根堆

        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) { // o1是p,o2=插入元素
                return o1[1] - o2[1];
            }
        });

注意： 此处如果
是 o1[1] - o2[1] 则是小根堆， 即元素出现的次数小的优先级高
是 o2[1] - o1[1] 则是大根堆， 即元素出现的次数大的优先级高

• 首先就是遍历整个数组，将元素和对应出现的次数存入到 map 集合中
• 然后创建一个优先级队列
• 并且往里面插入元素，如果队列中元素小于 K 个的时候直接插入
• 如果大于等于K个，就将即将要插入的元素的出现次数和堆顶元素（队头元素）进行比较，由于是小顶堆，所以如果即将插入的元素出现此处大于堆顶元素次数，就将堆顶元素弹出，再插入这个元素。不满足条件，就不插入
• 知道遍历完所有的集合，此时堆中的 K 个元素，就是出现频率最高的 K 个元素，用数组返回即可

    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();
        // 将数组放入集合中，key是元素本身，value是出现次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 创建一个小根堆，每一次加入一个元素，然后移除堆顶元素，因为是小根堆，所以堆顶元素是最小的
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            // 如果队列中元素少于 k 个
            if (priorityQueue.size() < k) {
                priorityQueue.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > priorityQueue.peek()[1]) {
                    priorityQueue.poll();
                    priorityQueue.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = priorityQueue.poll()[0];
        }
        return ans;
    }