239.滑动窗口最大值

题目链接：239.滑动窗口最大值 (opens new window)

这个题目的核心思想是该怎么实现用一个队列动态维护滑动窗口的最大值，用PriorityQueue不难想，什么时候该入队什么时候出队呢？

入队不用说，滑动窗口右移的时候肯定要入队，因为要获取整个窗口的最大值肯定要知道新加入滑动窗口的那个元素大小。正常来说，窗口右移我们是肯定要把窗口滑出的那个元素出队的，但是优先队列我们只能找到堆顶的元素，找不到特定元素。仔细想想其实也没必要，题目只要最大值，只要滑出的元素不是最大值，也就是队列中还存在更大的值，所以在更大的值出队前，滑出的元素出不出队并不影响结果。如果滑出的是最大值呢？那就可以出队了。怎么判断当前最大值是不是滑出的元素，判最大值需要数值，判滑出元素需要索引了，因此需要建立一个哈希表来判断最大值是不是滑出的元素，注意数值是key，索引是value。

思路到这就梳理的差不多了还有一个要注意的，如果存在相同的数，也就是最大值可能不止一个。是这样处理的，当数值相同时，我们把索引大的赋更高的优先级，也就是作为堆顶。其实这个无所谓的，即使前一个索引小的出队了，也会把后边相同值的列为堆顶，在C++中甚至可以不用定义pair的排序规则，默认按key排序。完整代码如下：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res=new int[nums.length-k+1];
        //自定义比较器让优先队列按值从大到小排序
        PriorityQueue<int[]> que=new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] pair1, int[] pair2) {
                // 这行也可以直接改为return pair2[0]-pair1[0];
                 return pair1[0]!=pair2[0]?pair2[0]-pair1[0]:pair2[1]-pair1[1];
            }
        });
        // 初始化队列
        for(int i=0;i<k;i++){
            que.add(new int[]{nums[i],i});
        }
        res[0]=que.element()[0];
        int j=1;
        for(int i=k;i<nums.length;i++){
            que.add(new int[]{nums[i],i});
            while(que.element()[1]<=i-k) que.remove();//最大值出队的情况           
            res[j++]=que.element()[0];//在加入新元素删除旧元素后让最大值出队
        }
        return res;
    }
}