首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

队列的最大值滑动窗口的最大值

解题思路 方法一:蛮力法 思路 扫描窗口k,得到最大值。对于长度为n的数组,算法时间复杂度O(nk) 显然不是最优解。...方法二:用两个栈实现队列 思路 面试题30中,我们实现过用两个栈实现了队列,可以在O(1)时间得到栈的最大值,也就可以得到队列的最大值。...方法三:双端队列 思路 参考解释: https://cuijiahua.com/blog/2018/02/basis_64.html 数组的第一个数字是2,把它存入队列中。...第二个数字是3,比2大,所以2不可能是滑动窗口中的最大值,因此把2从队列里删除,再把3存入队列中。第三个数字是4,比3大,同样的删3存4。此时滑动窗口中已经有3个数字,而它的最大值4位于队列的头部。...第四个数字2比4小,但是当4滑出之后它还是有可能成为最大值的,所以我们把2存入队列的尾部。下一个数字是6,比4和2都大,删4和2,存6。就这样依次进行,最大值永远位于队列的头部。

2.2K20
您找到你想要的搜索结果了吗?
是的
没有找到

滑动窗口最大值

滑动窗口最大值 给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。...示例 输入:nums = [1,3,-1,-3,5,3,6,7], k = 3 输出:[3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 -------------...我们可以通过维护一个单调递减的窗口来实现,当向右移动时左侧超出窗口的值弹出,因为需要的是窗口内的最大值,所以只要保证窗口内的值是递减的即可,即小于新加入的值全部弹出,最左端即为窗口最大值。...首先我们定义一个用来存储递减值的下标的窗口,以及存储最大值的组,之后循环给定的数组,如果当前遍历的数组值下标大于窗口大小并且递减下标窗口的第一个值是小于当前窗口,即第一个值在当前需要组合的窗口之外,就将其弹出...,之后从后向前遍历,如果递减窗口存在值且其中的值小于即将要加入的值就将其弹出,此时将当前遍历的值的下标加入递减窗口,最后如果窗口能够组合成k个就开始取最大值即递减窗口的第一个值,将其加入最大值组,循环结束后返回即可

63910

滑动窗口最大值

返回滑动窗口中的最大值。 分析 对于每个滑动窗口,我们可以使用 O(k)O(k) 的时间遍历其中的每一个元素,找出其中的最大值。...解题 优先队列方式 思路与算法 对于「最大值」,我们可以想到一种非常合适的数据结构,那就是优先队列(堆),其中的大根堆可以帮助我们实时维护一系列元素中的最大值。...每当我们向右移动窗口时,我们就可以把一个新的元素放入优先队列中,此时堆顶的元素就是堆中所有元素的最大值。...然而这个最大值可能并不在滑动窗口中,在这种情况下,这个值在数组 {nums}nums 中的位置出现在滑动窗口左边界的左侧。...此时,堆顶元素就是滑动窗口中的最大值

81400

滑动窗口之【和的最大值】&【最大值集合】

这是我参与11月更文挑战的第3天,活动详情查看:2021最后一次更文挑战 图片 本篇带来两道经典的关于滑动窗口的算法题,有兴趣可在控制台跑一跑~ 求和的最大值 题目来源:上一篇掘文《温故知新 ——...return maxVal }; const nums= [ 5, 7, 1, 4, 3, 6, 2, 9, 2 ] const k=5 maxSlidingWindow(nums,k) // 24 求最大值集合...返回滑动窗口中的最大值。...写一个函数来判断数组中最大的数; 初始化窗口,求最大值保存; 滑动窗口,再求最大值保存; 滑动直至完毕; 本瓜题解: /** * @param {number[]} nums * @param {number...用 Math.max() 来每次从窗口找最大值,时间复杂度是 O(n * k),仍然很大; 窗口固定,求最大值集合 在根本上是 单调队列 的问题!

39720

扫码

添加站长 进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

    运营活动

    活动名称
    广告关闭
    领券