【leetcode复健-9】239. 滑动窗口最大值-滑动窗口-队列-北京尧图网络

239. 滑动窗口最大值 - 力扣LeetCode给你一个整数数组nums有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例 1输入nums [1,3,-1,-3,5,3,6,7], k 3输出[3,3,5,5,6,7]解释滑动窗口的位置最大值 --------------- ----- [1 3 -1] -3 5 3 6 731 [3 -1 -3] 5 3 6 731 3 [-1 -3 5] 3 6 751 3 -1 [-3 5 3] 6 751 3 -1 -3 [5 3 6] 761 3 -1 -3 5 [3 6 7]7示例 2输入nums [1], k 1输出[1]提示1 nums.length 105-104 nums[i] 1041 k nums.length题目分析题目会给一个数组和一个窗口大小 k 让我们使用这个窗口在数组中滑动每次滑动找出窗口中的最大值并储存最后返回。这道题的优化思路很明显在于减小窗口内比较的时间复杂度为了最小化比较次数我们可以通过保存最大值和次大值来完成。我们需要知道窗口滑动时可能发生的情况1. 新值进来最大值依旧是最大值最大值需要更新2. 最大值出去次大值成为最大值当我们考虑到找最大值和次大值这一层思路的时候我们也需要想到另一个问题最大值左边的数值是无效的假设该窗口的次大值在最大值左边那就算等到最大值从左侧出去次大值也不会有任何用处因此我们的次大值应该从最大值右侧进行寻找由于遍历时我们可以观察到每一个最大值右侧的数值因此我们不应该也不需要对最大值右侧窗口中进行查找次大值而是每次循环直接比较好。通过这个思想我们可以借助队列完成这个队列中我们只存放三个我们最关心的数值下标存放下标是为了判断最大值是否掉出窗口最大值-次大值-当前数值。代码思路我们维护一个队列 q deque()其中我们需要保证 q[0] 位置一定是最大值q[1] 位置是次大值或者当前值q[2] 是当前值或无。遍历时无论如何将 q 中小于新值 x 的元素下标全部向右出队之后无论如何都将当前值下标加入队列。这一步就同时完成了找最大值和次大值的操作之后判断当前最大值下标 q[1] 是否超出范围是则向左出队一次。这样我们就保证了每次循环都可以直接将 nums[q[0]] 作为最大值存入数组中。正确代码class Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: from collections import deque q deque() lst [] for i, x in enumerate(nums): while q and x nums[q[-1]]: q.pop() q.append(i) if q[0] i - k 1: q.popleft() if i k - 1 : lst.a

【leetcode复健-9】239. 滑动窗口最大值-滑动窗口-队列

相关推荐

具身智能：TVA与世界模型的互补共生机制研究（总结列表）

海外版外卖私有化数据归属：部署域隔离与租户边界实践

Git stash 标准用法

更多资讯

Pro/E模型练习100例：建模入门必练的实操路径

红豆地球V1.182 7z包安装部署与问题排查指南

电子元器件比价平台：4 个真实比价渠道和方法

手机号归属地离线库：36万号段清洗入库与批量查询实战

外贸独立站如何选SEO服务商？避坑指南

Boost.Asio tcp::iostream：用C++流式编程简化TCP网络通信

今日更新

小波包能量谱原理与MATLAB实现：从频带分解到故障特征提取

基于LSTM的网易云音乐评论情感分析：数据清洗与模型调优实战

Alpha-Beta剪枝与极大极小值算法：博弈树搜索原理与实战优化

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？