1.堆与滑动窗口问题的结合
在《堆》一章解释过堆的大小一般是有限的，而且能直接返回当前位置下的最大值或者最小值。而该特征与滑动窗口结合，碰撞出的火花可以非常方便的解决一些特定场景的问题。
LeetCode239 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位，返回滑动窗口中的最大值。
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7这种方法我们在基础算法的堆部分介绍过。对于最大值、K个最大这种场景，优先队列（堆）是首先应该考虑的思路。大根堆可以帮助我们实时维护一系列元素中的最大值。
本题初始时，我们将数组 nums 的前 k个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。
我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 (num,index)，表示元素num 在数组中的下标为index。
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> pq = new Priority<>(new Comparator<int[]>(){
public int compare(int[] pair1, int[] pair2) {
return pair1[0]!=pair2 ? pair2[0]-pair1[0] : pair2[1]-pair1[1];
}
})
for(int i=0;i<k;i++){
pq.offer(new int[]{nums[i], i});
}
int[] ans = new int[n-k+1];
ans[0] = pq.peek()[0];
for(int i=k;k<n;k++){
pq.offer(new int[]{nums[i], i});
while(pq.peek()[1]<=i-k){
pq.poll();
}
ans[i-k+1] = pq.peek()[0];
}
return ans;
}下面是对代码每一句的解释：
int n = nums.length;：获取输入数组nums的长度，并将其存储在变量n中。PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {...});：创建一个优先队列pq，用于存储整数数组。优先队列中的每个元素都是一个包含两个整数的数组，第一个整数表示数组的值，第二个整数表示该值在原数组中的索引。for (int i = 0; i < k; ++i) { pq.offer(new int[]{nums[i], i}); }：将数组的前k个元素添加到优先队列中。int[] ans = new int[n - k + 1];：创建一个长度为n-k+1的整数数组ans，用于存储结果。ans[0] = pq.peek()[0];：将优先队列中的第一个元素（即当前窗口的最大值）赋值给结果数组的第一个元素。for (int i = k; i < n; ++i) { ... }：从第k个元素开始遍历数组，直到最后一个元素。pq.offer(new int[]{nums[i], i});：将当前元素添加到优先队列中。while (pq.peek()[1] <= i - k) { pq.poll(); }：如果优先队列中的元素索引小于等于当前窗口的起始索引减去k，则将其从优先队列中移除。这样可以确保优先队列中始终包含当前窗口内的元素。ans[i - k + 1] = pq.peek()[0];：将优先队列中的第一个元素（即当前窗口的最大值）赋值给结果数组的对应位置。return ans;：返回结果数组。
