LeetCode如何找出滑动窗口的最大值
发表于:2024-09-21 作者:千家信息网编辑
千家信息网最后更新 2024年09月21日,这篇文章给大家分享的是有关LeetCode如何找出滑动窗口的最大值的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。题目描述给定一个数组 nums 和滑动窗口的大小 k,请找出
千家信息网最后更新 2024年09月21日LeetCode如何找出滑动窗口的最大值
这篇文章给大家分享的是有关LeetCode如何找出滑动窗口的最大值的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
题目描述
给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。
你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ 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
题目思考
如果要求时间复杂度为 O(N), 该如何做?
解决方案
思路
一个比较容易想到的思路是暴力法, 即固定每个起点, 然后求它之后 k 个元素的最大值并依次加入结果中, 这样时间复杂度为 O(Nk), 当 k 很大的时候效率非常低, 该如何提高效率呢? 重新观察题目示例, 如果我们能够动态维护当前窗口的最大值, 那么在窗口移动的时候只需要用 O(1)时间返回这个值即可 窗口右移的时候, 如果新加入的值比原来的最大值还要大的话就好办, 直接更新最大值即可 但问题来了, 窗口右移意味着左边界也要向右移动, 如果正好之前的左边界是最大值该如何处理呢? 显然只保存最大值一个变量是不够的, 我们也需要保存第二大值, 第三大值... 根据上面的分析, 我们需要把这些值保存在一个单调的数据结构中, 一边是窗口里的最大值, 另一边则是最小值 窗口右移的时候, 按照顺序分为三部分操作: (当加入当前值后窗口长度会超过 k 时, 即 right>=k
) 移除老的左边界值: 如果它恰好是最大值, 也移除单调数据结构中对应的值加入新的右边界值: 此时需要先不断移除最小值, 直到当前新值成为新的最小值再插入, 因为更小的值绝不可能成为最大值的候选项( 又旧, 值又小) (当加入当前值后窗口长度达到 k 时, 即 right>=k-1
) 将单调数据结构中保存的最大值加入最终结果中注意上述三个步骤中 3 必须是最后一步, 因为要先调整完当前窗口的最大最小值才行, 而 1 和 2 可以互换位置, 因为可以先处理左边界, 也可以先处理右边界 根据上述过程, 我们只需要处理头和尾的插入删除操作, 很显然 双端队列就是最合适的数据结构, 两种操作都只需要 O(1)时间 下面代码对必要的步骤有详细的解释, 特别是对步骤 1 和 2 的一些关键点的解释, 方便大家理解
复杂度
时间复杂度 O(N): 每个值最多加入和移出双端队列各一次, 总共 2N 次操作, 所以时间复杂度是 O(N) 空间复杂度 O(k): 双端队列最多存 k 个值
代码
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# 单调双端队列, 左边存窗口最小值, 右边存窗口最大值
q = collections.deque()
res = []
left = 0
for right in range(len(nums)):
# 步骤1 (当加入当前值后窗口长度会超过 k 时, 即right>=k) - 移除老的左边界值: 如果它恰好是最大值, 也移除队列尾
# 注意左边界如果不是最大值的话, 不会存在于队列中, 因为它后面总有更大的值将左边界从队列中淘汰出去 (步骤2的操作)
if right >= k:
if nums[left] == q[-1]:
q.pop()
left += 1
# 步骤2 (可以和步骤1互换位置) - 加入新的右边界值: 此时需要先不断移除队列左侧最小值, 直到当前新值成为新的最小值再插入左侧, 因为更小的值绝不可能成为最大值的候选项(又旧, 值又小)
# 注意这里需要是小于而不能是小于等于, 因为如果当最小值等于当前值且都被移除的话, 如果它恰好也是最大值, 那么下次移除左边界的时候就会错误地将当前的值给移除, 而不是移除左边界对应的那个值, 这样会导致后面的最大值计算出现错误
while q and q[0] < nums[right]:
q.popleft()
q.appendleft(nums[right])
# 步骤3 (当加入当前值后窗口长度达到 k 时, 即right>=k-1) - 将队列右侧最大值加入最终结果中
if right >= k - 1:
res.append(q[-1])
return res
感谢各位的阅读!关于"LeetCode如何找出滑动窗口的最大值"这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
最大
最大值
队列
最小
步骤
复杂
复杂度
时间
时候
单调
右边
数据
数据结构
结构
长度
题目
位置
数组
结果
处理
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
网络服务器配设与管理
.数据库系统
长沙简商网络技术有限公司
和平精英服务器进不去什么情况
网站数据库能恢复什么软件
主流网络技术有哪些
达梦数据库dump全量
魔兽世界美服服务器
个性化网络技术原理
网络安全技术软件下载
湖南服务器机柜定做高档虚拟主机
中英词库 数据库
上海ar软件开发哪家好
网络技术都忙得什么
linux平台搭建网关服务器
绵阳市app软件开发公司
网络安全征文800字以上
贵州青莽互联网科技有限
学生网络安全教育班会
服务器cpu与内存搭配
电子商务的网络安全
.数据库系统
swiss数据库
秒表软件开发主流程图
建网站怎么用国外的服务器
x86向arm服务器移植
游戏小说软件开发
网络安全日志上网行为管理
VFP数据库技术论文
甘肃运营网络技术服务代理商