队列

分类

单调队列

队列元素单调递减或者单调递增

优先队列

大顶堆或者小顶堆

239. 滑动窗口最大值

解法一：优先队列

对于「最大值」问题，可以考虑优先队列，大顶堆可以实时维护一系列元素中的最大值
对于本题来说，初始时，我们将数组nums的前k的元素放入优先队列中。每当窗口右移时，就可以吧一个新的元素放入优先队列中，此时堆中有k+1个元素，且堆顶为这k+1个元素的最大值。但是这个最大值可能不在滑动窗口中，也就是说最大值在滑动窗口左边界的左侧，因此可以考虑优先队列中同时保存值和下标。
不断移除堆顶元素，如果他的下标小于窗口左边界的话，直到堆顶元素确实在滑动窗口中。如果堆的其他位置也有窗口外元素，只要他不是最大的，就不影响，堆中不一定必须有k个元素。

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        // 1. 优先队列存放的是二元组(num,index) : 大顶堆（元素大小不同按元素大小排列，元素大小相同按下标进行排列）
            // num :   是为了比较元素大小
            // index : 是为了判断窗口的大小是否超出范围
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] pair1,int[] pair2){
                //自定义排序顺序，降序排列，让值大的在前面，如果值相等，让下标大的在前面
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0]:pair2[1] - pair1[1];
            }
        });
        // 2. 优选队列初始化 : k个元素的堆
        for(int i = 0;i < k;i++){
            pq.offer(new int[]{nums[i],i});
        }
        // 3. 处理堆逻辑
        int[] res = new int[n - k + 1];         // 初始化结果数组长度 ：一共有 n - k + 1个窗口
        res[0] = pq.peek()[0];                  // 初始化res[0] ： 拿出目前堆顶的元素
        for(int i = k;i < n;i++){               // 向右移动滑动窗口
            pq.offer(new int[]{nums[i],i});     // 加入大顶堆中
            while(pq.peek()[1] <= i - k){       // 将下标不在滑动窗口中的堆顶元素都干掉
                pq.poll();                      // 维护：堆的大小就是滑动窗口的大小
            }   
            res[i - k + 1] = pq.peek()[0];      // 此时堆顶元素就是滑动窗口的最大值
        }
        return res;
    }

解法二：单调队列

自定义单调队列

class MyQueue {
    Deque<Integer> deque = new LinkedList<>();
    //弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
    //同时判断队列当前是否为空
    void poll(int val) {
        if (!deque.isEmpty() && val == deque.peek()) {
            deque.poll();
        }
    }
    //添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
    //保证队列元素单调递减
    //比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
    void add(int val) {
        while (!deque.isEmpty() && val > deque.getLast()) {
            deque.removeLast();
        }
        deque.add(val);
    }
    //队列队顶元素始终为最大值
    int peek() {
        return deque.peek();
    }
}

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

使用双端队列模拟

感觉跟上面的优先队列思路差不多，都是元素放进去不急着删除，如果他是队列头，即最大值，这时候才判断他是不是在窗口中，当一个新元素进来时，比他小的就没存在的必要了

    public int[] maxSlidingWindow(int[] nums, int k){
        int n = nums.length;
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int[] ans = new int[n - k + 1];
        int idx = 0;
        for (int i = 0; i < n; ++i){
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while (!deque.isEmpty() && deque.getFirst() < i - k + 1){
                deque.pollFirst();
            }
            // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
            while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]){
                deque.pollLast();
            }
            deque.addLast(i);
            if (i >= k-1){
                ans[idx++] = nums[deque.getFirst()];
            }
        }
        return ans;
    }

347. 前 K 个高频元素

构建的是小顶堆，因此要抛出最小的，留下K个最大的
new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

    public int[] topKFrequent(int[] nums, int k) {
        int[] res = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums){
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        //棋差一招就是在这，用int[]不好判断，不是字符串
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o1.getValue() - o2.getValue();
            }
        });
        for (Map.Entry<Integer, Integer> entry : entries){
            pq.offer(entry);
            if (pq.size() > k){
                pq.poll();
            }
        }
        for (int i = 0; i < k; ++i){
            res[i] = pq.poll().getKey();
        }
        return res;
    }