day12 休息 day13 栈与队列part3

239. 滑动窗口最大值

困难
提示
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        MyQueue window = new MyQueue();
        int res[] = new int[nums.length - k + 1]; //返回数组

        for (int i = 0; i < nums.length; i++){
            if (i < k - 1){
                //先填满窗口的前 k - 1
                window.push(nums[i]);
            }else {
                // 窗口向前滑动，加入新数字
                window.push(nums[i]);
                // 记录当前窗口的最大值
                res[i - k + 1] = window.max();
                // 移出旧数字
                window.pop(nums[i - k + 1]);
            }
        }
        return res;
    }
}

//自定义单调队列
class MyQueue {
    Deque<Integer> maxDeque = new LinkedList<>();
    public void push(int n){
        // 将队列里小于n的全部删除
        while (!maxDeque.isEmpty() && maxDeque.getLast() < n){
            maxDeque.pollLast();
        }
        // 然后将 n 加入尾部
        maxDeque.addLast(n);
    }
    public int max(){
        return maxDeque.getFirst();
    }
    // 如果要移出的这个旧数字恰好是单调队列的最大值（队头），那么把队头移出
    public void pop(int n){
        if (n == maxDeque.getFirst()){
            maxDeque.pollFirst();
        }
    }
}

以下内容引用自：一题四解：滑动窗口的最大值 - 豁大王的文章 - 知乎
https://zhuanlan.zhihu.com/p/506553409

347. 前 K 个高频元素

中等
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案

难点：不懂大顶堆小顶堆，也不会相应语法，以下是扫盲链接：

①java小顶堆、大顶堆实现和使用（例题：力扣347.前K个高频元素）
②大顶堆小顶堆
③优先队列PriorityQueue＜＞ (a, b) -＞ b - a详细介绍：链接

这个题大顶堆小顶堆都能实现，大顶堆就是无脑全部加入，取前k个，小顶堆更巧妙点，
以小顶堆为例来做：
这个容易默写一点：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 优先级队列，为了避免复杂 api 操作，pq 存储数组
        // lambda 表达式设置优先级队列从大到小存储 o1 - o2 为从小到大，o2 - o1 反之
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        int[] res = new int[k]; // 答案数组为 k 个元素
        Map<Integer, Integer> map = new HashMap<>(); // 记录元素出现次数
        for(int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        for(var x : map.entrySet()) { // entrySet 获取 k-v Set 集合
            // 将 kv 转化成数组
            int[] tmp = new int[2];
            tmp[0] = x.getKey();
            tmp[1] = x.getValue();
            pq.offer(tmp);
            // 下面的代码是根据小根堆实现的，我只保留优先队列的最后的k个，只要超出了k我就将最小的弹出，剩余的k个就是答案
            if(pq.size() > k) {
                pq.poll();
            }
        }
        for(int i = 0; i < k; i ++) {
            res[i] = pq.poll()[0]; // 获取优先队列里的元素
        }
        return res;
    }
}

这个调用了没接触过的东西……，不太容易默写，但是是在力扣上亲自敲过的。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();//key为数组元素值,val为对应出现次数

        for (int i : nums) {
            // 这样写更优雅，而且只有一行
            // for (int v : nums){map.put(v, map.getOrDefault(v, 0) + 1);}
            if (map.containsKey(i)) {
                map.put(i, map.get(i) + 1);
            } else {
                map.put(i, 1);
            }
        }
        //在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
        //出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {// 小顶堆只需要维持k个元素有序
            if (pq.size() < k) { 
                pq.add(new int[] { entry.getKey(), entry.getValue() });
            } else {
                if (entry.getValue() > pq.peek()[1]) { //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                    pq.poll(); //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
                    pq.add(new int[] { entry.getKey(), entry.getValue() });
                }
            }
        }
        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            res[i] = pq.poll()[0]; //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
        }
        return res;
    }
}