239. 滑动窗口最大值

思路：

• 使用优先队列解决问题，因为一个滑动窗口取最大值
• 一看就符合大顶堆的特征，每次取堆顶就是最大值。
• 在移动窗口的时候，正常应该队列新增新进入窗口的元素，删除出了窗口的元素。
• 不过这时候可以使用，懒删除。就是需要删除的元素可能不会影响堆顶，也就不需要立刻删除。
• 只有取到堆顶并且发现堆顶不合法的时候，再进行一波集中的删除堆顶，直到找到一个合法的堆顶

�

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        //定义一个pair的优先队列，从大到小排序
        //pair 的key是实际值，value是下标
        PriorityQueue<Pair<Integer,Integer>> queue = new PriorityQueue<Pair<Integer,Integer>>(new Comparator<Pair<Integer,Integer>>() {
            @Override
            public int compare(Pair<Integer,Integer> o1, Pair<Integer,Integer> o2) {
                return o2.getKey().compareTo(o1.getKey());
            }
        });
        for(int i = 0 ; i < nums.length;i ++){
            //直接往优先队列里面入队
            queue.offer(new Pair<>(nums[i],i ));
            //当 i >= k-1 了，说明滑动窗口已满，需要开始滑动了，那么每一次滑动就需要取出队头（当前最大值）写入答案中
            if(i >= (k-1)){
                //取出队头时要判断队头是否在滑动窗口中，如果不在窗口中则继续取队头直到取到了一个再窗口中的队头
                //下标是否在窗口中，就看  下表 是否 <= i-k  如果是，则不在窗口中
                //这个叫做懒删除。就是当队列新增一个元素的时候，不去删除窗口外的一个元素。只有当需要被删除的元素影响到队头最大值的时候才删除。
                while (queue.peek().getValue() <= (i - k)){
                    queue.poll();
                }
                Integer windowMax = queue.peek().getKey();
                res[i - k + 1] = windowMax;
            }
        }
        return res;
    }
}