1. 堆与滑动窗口问题结合

题目

LeetCode239 给你一个整数数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧，你可以看到在滑动窗口内的k个数字，滑动窗口每次只向右移动一位，返回滑动窗口中的最大值。

思路

对于最大值、k个最大值这种场景，优先队列（堆）是首先应该考虑的思路。大根堆可以帮我们实时维护一系列中的最大值。

        把nums中前k个元素放入队中，作为初始值，第一个最大值就可以知道了，每次向右移动滑动窗口的时候，我们可以取出其中的最大值，当然最大值不一定在滑动窗口中的第一个元素，（如图中第6行第7行）因为窗口的大小固定，所以最多k-1次移动取出最大值，最少直接在首位取出，所以堆的大小其实是固定的，并不会太大，因为我们需要知道堆中元素在数组中的索引位置，索引存储二元数组（num，index）。

整个过程大概就是边向右滑动边取出最大值的过程，当pq.peek()[1] <= i - k的时候，最大的元素是在窗口左端的左侧，在窗口外面，需要删除。

代码

    public int[] maxSlidingWindow(int[] nums, int k){int n = nums.length;PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {//正数单调递减return o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[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; i < n; i++) {pq.offer(new int[]{nums[i],i});//判断最大值是否是窗口的第一个元素，是第一个元素因为窗口需要向前滑动，窗口大小固定，所以窗口中第一个元素需要移除while (pq.peek()[1] <= i - k){pq.poll();}ans[i - k + 1] = pq.peek()[0];}return ans;}