滑动窗口最大值LeetCode-Book 中基于单调队列的 O(n) 解法全解析【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读本文以 LeetCode-Book 仓库中 239. 滑动窗口最大值解题文档 为核心系统讲解如何在窗口每次滑动后将获取窗口内最大值的时间复杂度从暴力法的 O(k) 降到 O(1)从而把整题的总复杂度压缩到 O(n)。文章从暴力法的时间瓶颈出发推导单调队列的两条核心不变量并给出 Python、Java、C 三种语言、两种写法的完整可运行代码最后结合仓库源码中的测试用例与依赖结构说明如何在本仓库中直接验证解法。问题本质滑动窗口的最大值为什么难设数组为nums窗口大小为k。仓库源码中给出了标准的测试用例nums [1, 3, -1, -3, 5, 3, 6, 7]k 3 期望输出 [3, 3, 5, 5, 6, 7]窗口区间可记为[i, j]其中j - i 1 k窗口内最大值为x_j。当窗口向前滑动一格区间变为[i1, j1]等价于添加nums[j1]、删除nums[i]两步操作。只添不删时O(1) 即可更新最大值若窗口只在右侧添加新元素nums[j1]那么新窗口的最大值可以直接通过一次比较得到x_{j1} max(x_j, nums[j1])这是 O(1) 的。难点在于删除被删元素可能就是当前最大值然而窗口滑动同时还会删除左侧元素nums[i]。问题在于被删除的nums[i]可能恰好就是窗口内唯一的最大值x_j。此时最大值断档无法用上式递推只能退化为遍历整个窗口区间重新计算x_{j1} max(nums[i1], ..., nums[j1])这一步需要 O(k) 时间。暴力法的时间复杂度根据上述分析暴力法的时间复杂度为数组长度为 n共存在(n - k 1)个窗口每个窗口线性遍历求最大值耗时 O(k)总复杂度为O((n-k1)·k) ≈ O(nk)。当 k 接近 n/2 时这是平方级开销在大数组上不可接受。本题难点如何在每次窗口滑动后将获取窗口内最大值的时间复杂度从 O(k) 降低至 O(1)。单调队列把窗口看作双端队列从最小栈到单调队列的类比回忆经典题最小栈min-stack它借助单调栈实现了在随意入栈、出栈的情况下 O(1) 获取栈内最小值。本题思路完全一致唯一差异在于出栈的方向最小栈的出栈操作删除的是列表尾部元素窗口滑动删除的是列表首部元素。因此窗口对应的数据结构是双端队列deque本题采用单调队列即可解决问题它既能在尾部入队、出队对应新元素加入窗口也能在头部出队对应旧元素滑出窗口。单调队列的两条不变量遍历数组时每轮循环保证单调队列deque满足deque内仅包含窗口内的元素每轮窗口滑动移除了元素nums[i-1]需将deque中对应的元素一起删除若它还在队列中deque内的元素非严格递减每轮窗口滑动添加了元素nums[j1]需将deque内所有 nums[j1]的元素从尾部弹出因为它们不可能再成为后续窗口的最大值。这两条不变量合起来保证队首元素永远是当前窗口的最大值取队首即 O(1) 得到答案。算法流程初始化双端队列deque结果列表res数组长度n滑动窗口左边界范围i ∈ [1-k, n-k]右边界范围j ∈ [0, n-1]若i 0且队首元素deque[0] nums[i-1]被删除元素队首元素出队删除deque内所有 nums[j]的元素以保持deque递减将nums[j]添加至deque尾部若已形成窗口即i ≥ 0将窗口最大值队首元素deque[0]添加至结果列表res返回值返回结果列表res。代码实现一单循环写法i、j 同步推进这一写法让左右边界i、j在同一个循环中同步移动逻辑紧凑。Python 中通过zip(range(), range())实现左右边界的并行遍历Java 与 C 则在for循环的迭代式中同时递增i与j。class Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: deque collections.deque() res, n [], len(nums) for i, j in zip(range(1 - k, n 1 - k), range(n)): # 删除 deque 中对应的 nums[i-1] if i 0 and deque[0] nums[i - 1]: deque.popleft() # 保持 deque 递减 while deque and deque[-1] nums[j]: deque.pop() deque.append(nums[j]) # 记录窗口最大值 if i 0: res.append(deque[0]) return resclass Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums.length 0 || k 0) return new int[0]; DequeInteger deque new LinkedList(); int[] res new int[nums.length - k 1]; for(int j 0, i 1 - k; j nums.length; i, j) { // 删除 deque 中对应的 nums[i-1] if(i 0 deque.peekFirst() nums[i - 1]) deque.removeFirst(); // 保持 deque 递减 while(!deque.isEmpty() deque.peekLast() nums[j]) deque.removeLast(); deque.addLast(nums[j]); // 记录窗口最大值 if(i 0) res[i] deque.peekFirst(); } return res; } }class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { if(nums.size() 0 || k 0) return {}; dequeint deque; vectorint res(nums.size() - k 1); for(int j 0, i 1 - k; j nums.size(); i, j) { // 删除 deque 中对应的 nums[i-1] if(i 0 deque.front() nums[i - 1]) deque.pop_front(); // 保持 deque 递减 while(!deque.empty() deque.back() nums[j]) deque.pop_back(); deque.push_back(nums[j]); // 记录窗口最大值 if(i 0) res[i] deque.front(); } return res; } };代码要点初始i 1 - kj 0此时窗口尚未成形左边界为负只执行入队与维护递减的操作不记录结果队首删除使用值相等即删的判断由于队列保持非严格递减且被滑出窗口的元素若仍在队列中必然位于队首比它新的元素都更大或相等会把它挤到队首或被弹出因此deque[0] nums[i-1]是可靠的出队条件出队判断用而非相等的元素保留在队列中这样当被删除元素与队首值相等时能正确执行队首出队避免把重复最大值提前误删导致答案缺失。代码实现二两阶段循环写法上面的写法在每一轮都执行i 0、i 0的判断。另一种更直观的思路是将未形成窗口前 k 个元素与形成窗口后从第 k1 个元素起拆分为两个循环。代码虽然变长但减少了每轮循环中的冗余判断语义也更清晰适合面试中先讲思路再落代码。class Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: if not nums or k 0: return [] deque collections.deque() # 未形成窗口 for i in range(k): while deque and deque[-1] nums[i]: deque.pop() deque.append(nums[i]) res [deque[0]] # 形成窗口后 for i in range(k, len(nums)): if deque[0] nums[i - k]: deque.popleft() while deque and deque[-1] nums[i]: deque.pop() deque.append(nums[i]) res.append(deque[0]) return resclass Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums.length 0 || k 0) return new int[0]; DequeInteger deque new LinkedList(); int[] res new int[nums.length - k 1]; // 未形成窗口 for(int i 0; i k; i) { while(!deque.isEmpty() deque.peekLast() nums[i]) deque.removeLast(); deque.addLast(nums[i]); } res[0] deque.peekFirst(); // 形成窗口后 for(int i k; i nums.length; i) { if(deque.peekFirst() nums[i - k]) deque.removeFirst(); while(!deque.isEmpty() deque.peekLast() nums[i]) deque.removeLast(); deque.addLast(nums[i]); res[i - k 1] deque.peekFirst(); } return res; } }class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { if(nums.size() 0 || k 0) return {}; dequeint deque; vectorint res(nums.size() - k 1); // 未形成窗口 for(int i 0; i k; i) { while(!deque.empty() deque.back() nums[i]) deque.pop_back(); deque.push_back(nums[i]); } res[0] deque.front(); // 形成窗口后 for(int i k; i nums.size(); i) { if(deque.front() nums[i - k]) deque.pop_front(); while(!deque.empty() deque.back() nums[i]) deque.pop_back(); deque.push_back(nums[i]); res[i - k 1] deque.front(); } return res; } };仓库源码测试用例与运行验证代码文件组织本仓库在selected_coding_interview/codes/下按语言组织本题代码两阶段写法的 Python 实现即为写法一对应文件Pythonlc_239_sliding_window_maximum_s1.py单循环写法、lc_239_sliding_window_maximum_s2.py两阶段写法Javalc_239_sliding_window_maximum_s1.java、lc_239_sliding_window_maximum_s2.javaClc_239_sliding_window_maximum_s1.cpp、lc_239_sliding_window_maximum_s2.cpp。测试用例驱动的验证方式Python 与 Java 源文件在Solution之外都内嵌了完全一致的测试用例与驱动代码可直接运行验证test_input_nums [1, 3, -1, -3, 5, 3, 6, 7] test_input_k 3 expected_output [3, 3, 5, 5, 6, 7]以该用例手动推演单调队列的运行过程窗口大小为 3处理1, 33弹出1队列[3]处理-1队列[3, -1]第一个窗口[1,3,-1]最大值为队首3处理-3队列[3, -1, -3]窗口[3,-1,-3]最大值3处理55依次弹出-3、-1、3队列[5]窗口[-1,-3,5]最大值5处理3队列[5, 3]窗口[-3,5,3]最大值5处理66弹出3、5队列[6]窗口[5,3,6]最大值6处理77弹出6队列[7]窗口[3,6,7]最大值7。最终结果[3, 3, 5, 5, 6, 7]与期望输出完全一致。注意第 5、6 步旧元素如-3在不在队首时靠队首元素等于被删除元素才出队的判断自然跳过这正是单调队列能正确工作的关键细节。依赖与运行环境Python 解法文件通过from include import *引入公共依赖见 include/init.py其中导入了collections提供双端队列deque与typing.List用于类型标注List[int]。C 解法通过#include ../include/include.hpp引入公共头文件。值得注意的是C 两个文件的main函数中测试用例仍标记为TODO见 lc_239_sliding_window_maximum_s1.cpp其核心Solution逻辑已完整实现读者可参照 Python/Java 版本补充驱动代码后本地编译验证。复杂度分析时间复杂度 O(n)其中 n 为数组nums的长度。线性遍历nums本身占用 O(n)单调队列的每个元素最多入队一次、出队一次因此入队/出队操作合计占用 O(2n)即 O(n)。空间复杂度 O(k)双端队列deque中最多同时存储 k 个元素即窗口大小与窗口规模成正比不随 n 增长。相比暴力法的 O(nk)单调队列方案在时间上取得了质的提升这正是本题的考察核心把滑动窗口 最值问题转化为维护一个支持头部删除、尾部插入的双端队列上的单调结构。总结与延伸本文完整覆盖了 LeetCode 239 的单调队列解法从添加易、删除难的窗口特性出发推导出暴力法 O(nk) 的瓶颈借助最小栈的类比引出双端队列与单调队列的两条不变量给出单循环、两阶段两种写法的 Python / Java / C 三语言实现结合仓库源码中的测试用例验证正确性并给出 O(n) 时间、O(k) 空间的复杂度结论。单调队列的思想可以推广到一类定长滑动窗口求最值问题例如求滑动窗口最小值把递减改为递增即可、滑动窗口中位数等变体。掌握用双端队列维护窗口内候选集这一核心模型是解决该类问题的一劳永逸之策。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考