临清网站建设价格,logo设计公司哪家好,网站系统建设合作合同范本,青岛公司logo设计文章目录 前言堆与滑动窗口结合的问题总结 前言 提示#xff1a;不论记忆多么痛苦#xff0c;它属于过去#xff0c;已经逝去了#xff0c;我们为什么还执着于它并让它代表我们#xff1f;我们就这样#xff0c;所以#xff0c;我们受苦。 --丹津葩默 这个还是一个比较重… 文章目录 前言堆与滑动窗口结合的问题总结 前言 提示不论记忆多么痛苦它属于过去已经逝去了我们为什么还执着于它并让它代表我们我们就这样所以我们受苦。 --丹津·葩默 这个还是一个比较重要的问题呢滑动窗口结合堆的特性解决一些问题。 堆与滑动窗口结合的问题
在堆的一章我们解释了堆的有限性但是返回当前位置的最大值或最小值。这除了堆没有更合适的了。推荐算法通过村第十四关-堆|白银笔记|经典问题-CSDN博客
然而这结合滑动窗口可以擦出不一样的火花非常适合一些特定场景下解决一些题目
239. 滑动窗口最大值 - 力扣LeetCode 这种方式我们在基础算法的堆中已经说过这种问题了对于找最大值、K个最大的这种场景优先队列堆是首选。
大致思路我们将数组nums的前k个元素放入优先队列中每当我们向右移动窗口时我们就可以把一个新的元素放入优先队列中此时堆顶的元素就是所有元素的最大值。然而这个最大值可能并不在滑动窗口中在这种情况下这个数组的中间的位置出现在滑动窗口左边界的左侧。因此当我们后序继续移动窗口的时候这个值就永远不可能出现在滑动窗口中了我们可以将其永久地从优先队列中移除。
我们不断的移除堆顶的元素知道其确实出现在滑动窗口中此时堆顶的元素就是滑动窗口中的最大值为了方便判断堆顶元素与滑动的窗口的位置关系我们可以在优先队列总存储二元组numindex表示元素num在数组中的下标。 /*** 滑动窗口最大值* param nums* param k* return*/public static int[] maxSlidingWindow(int[] nums, int k) {int n nums.length;// 二元组处理 提高 (ac)/2 格PriorityQueueint[] pq new PriorityQueueint[](new Comparatorint[]() {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});// 确保在堆中if (pq.peek()[1] i - k){pq.poll();}ans[i - k 1] pq.peek()[0];}return ans;}当然了本地还有其他解法比如双向队列单调队了啦。这个后面研究哈不过都没这个直接容易提升
二元组处理 提高 (ac)/2 格。
喜欢拓展的朋友可以看看下一题如果找中位数怎么处理呢可以使用两个堆做处理推荐题目⭐⭐⭐⭐
400. 第 N 位数字 - 力扣LeetCode 总结
提示滑动窗口双指针堆优先队列滑动窗口和堆的结合二元组思想 如果有帮助到你请给题解点个赞和收藏让更多的人看到 ~ (▔□▔)/
如有不理解的地方欢迎你在评论区给我留言我都会逐一回复 ~
也欢迎你 关注我 喜欢交朋友喜欢一起探讨问题。
