【LeetCode刷题-滑动窗口】-- 239.滑动窗口最大值

239.滑动窗口最大值

分析：

方法：优先队列

对于最大值，可以使用优先队列(堆)，其中的大根堆可以帮助实时维护一系列元素中的最大值

在本题中，初始时，将数组nums的前k个元素放入优先队列中，每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值，然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组nums中的位置出现在滑动窗口左边界的左侧，因此我们后续继续向右移动滑动窗口，这个值就永远不可能出现在滑动窗口中了，就可以将其永久地从优先队列中移除

不断移除堆顶的元素，直到其确实出现在滑动窗口中，此时堆顶元素就是滑动窗口中的最大值，为了方便判断堆顶元素与滑动窗口的关系，可以在优先队列中存储二元组(num,index)，表示元素num在数组的下标为index

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        //1.优先队列存放的是二元组(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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27