算法通过村第十六关-滑动窗口|黄金笔记|结合堆的应用

---

前言

---

提示：不论记忆多么痛苦，它属于过去，已经逝去了，我们为什么还执着于它并让它代表我们？我们就这样，所以，我们受苦。 --丹津·葩默

这个还是一个比较重要的问题呢，滑动窗口结合堆的特性解决一些问题。

堆与滑动窗口结合的问题

在堆的一章，我们解释了，堆的有限性，但是返回当前位置的最大值或最小值。这除了堆，没有更合适的了。推荐：算法通过村第十四关-堆|白银笔记|经典问题-CSDN博客

然而这结合滑动窗口，可以擦出不一样的火花，非常适合一些特定场景下解决一些题目

239. 滑动窗口最大值 - 力扣（LeetCode）

这种方式，我们在基础算法的堆中已经说过这种问题了，对于找最大值、K个最大的这种场景，优先队列（堆）是首选。

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

我们不断的移除堆顶的元素，知道其确实出现在滑动窗口中，此时堆顶的元素就是滑动窗口中的最大值，为了方便判断堆顶元素与滑动的窗口的位置关系，我们可以在优先队列总存储二元组（num，index）表示元素num在数组中的下标。

    /**
     * 滑动窗口最大值
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        // 二元组处理 提高 (a+c)/2 格
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public 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});
            // 确保在堆中
            if (pq.peek()[1] < i - k){
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
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
28
29
30
31
32
33

当然了，本地还有其他解法，比如双向队列，单调队了啦。这个后面研究哈，不过都没这个直接，容易提升

二元组处理 提高 (a+c)/2 格。

喜欢拓展的朋友可以看看下一题：如果找中位数怎么处理呢？可以使用两个堆做处理，推荐题目⭐⭐⭐⭐：

400. 第 N 位数字 - 力扣（LeetCode）

---

总结

提示：滑动窗口；双指针；堆（优先队列）；滑动窗口和堆的结合；二元组思想

---

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

如有不理解的地方，欢迎你在评论区给我留言，我都会逐一回复 ~

也欢迎你 关注我 ，喜欢交朋友，喜欢一起探讨问题。