训练营day13：栈与队列3

239. 滑动窗口最大值

https://leetcode.cn/problems/sliding-window-maximum/description/
题后感：
该题的核心解法是用一个临时的队列来存每次滑动窗口的内几个值，临时队列中需要包含最大值，同时临时队列中在特殊情况下又不仅仅是包含最大值，例如：如果窗口首位就是最大值，那么就需要保存后面的值，因为如果此刻滑动窗口移动，那么首位被删除了，临时队列里没有需要保存剩下的数，我们就计算不出新的滑动窗口里的最大值了。
=》因此，该队列里可以保存的是最大值及后面小于等于该值的所有值，队列的头部是最大值，后面是无序的，用这种方法就解决了上面说的问题
窗口内的数据大概可分为两种情况：
第一种，最大值出现在窗口首位，移动滑动窗口，单调队列里对应的值被删除，其他元素还在；
第二种，最大值出现在窗口首位之后，移动滑动窗口，单调队列里没有变化。

同时，还有一个细节的点，增加元素的时候「小于等于最大值」也会被加进去，这样如果出现了两个相同的最大值，就能保证删除的时候是正常的。

（刚开始之前我想在队列里保存窗口内最大值及窗口非首位的最大值，即最大和次大，每次滑动就把去掉之前窗口的首位值就可，这样的话问题是该种方法就涉及到位置的交换，就变复杂了）

class MyQueue {
    Deque<Integer> deque = new LinkedList<>();
    // 增加元素，只要前面元素比增加元素大，就逐一删除，以保证单调性
    public void add(int value) {
        while (!deque.isEmpty() && value > deque.getLast()) {
            deque.removeLast();
        }
        deque.add(value);
    }

    // 移除头部元素，只判断第一个元素就行
    public void poll(int value) {
        if (!deque.isEmpty() && deque.peek() == value) {
            deque.poll();
        }
    }

    public int peek() {
        return deque.peek();
    }
}
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        int[] result = new int[nums.length - k + 1];
        MyQueue tempDeque = new MyQueue();
        for(int i = 0;i < k;i++) {
            tempDeque.add(nums[i]);
        }
        int tempIndex = 0;
        result[tempIndex++] = tempDeque.peek();
        for(int i = k;i < nums.length; i++) {
            tempDeque.poll(nums[i - k]);
            tempDeque.add(nums[i]);
            result[tempIndex++] = tempDeque.peek();
        }
        return result;
    } 
}

347.前 K 个高频元素

https://leetcode.cn/problems/top-k-frequent-elements/description/
题后感：
思路逻辑很简单（看题解后），主要是利用优先级队列大（小）顶堆进行排序，但是这个优先级队列大小顶堆的实现还真是别扭，需要记住。
“lambda 表达式设置优先级队列从大到小存储 o1 - o2 为从小到大，o2 - o1 反之”

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> tempMap = new HashMap<>();
        // map记录次数
        for(int i = 0;i < nums.length;i++) {
            tempMap.put(nums[i], tempMap.getOrDefault(nums[i], 0) + 1);
        }
        // 利用优先级队列建只放k个元素的小顶堆，超过数量就弹出父节点（最小）
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[1] - o2[1]);
        for(var var : tempMap.entrySet()) {
            // kv转成数组，放到优先级队列里
            int[] temp = new int[2];
            temp[0] = var.getKey();
            temp[1] = var.getValue();
            pq.offer(temp);
            if(pq.size() > k) {
                pq.poll();
            }
        }
        int[] result = new int[k];
        for (int i = 0; i<k; i++) {
            result[i] = pq.poll()[0];
        }

        return result;
    }
}

训练营day13：栈与队列3