力扣239滑动窗口最大值：从暴力到单调队列O(n)解法

每天刷一道算法题今天轮到力扣 239 滑动窗口最大值。这道题在面试和算法练习里出现频率非常高也是很多人心中“单调队列”的入门第一课同时它又是一个非常典型的“暴力解法和最优解法差距极大”的样本。题目描述很简单给你一个数组 nums 和一个窗口大小 k窗口从数组最左边滑到最右边每次滑一格返回每个窗口里的最大值。如果你刚开始准备算法面试对“滑动窗口”的理解还停留在“双指针维护一段区间”的阶段那么这篇就是专门为你准备的。我会从最笨的暴力解法开始逐步推导出能用 O(n) 时间解决的单调队列写法把每一步的思考过程、代码细节、容易踩的坑都摊开讲清楚。读完你不仅能 AC 这道题还能顺手拿下后面好几道同类题目。1. 先读懂题滑动窗口到底在滑什么1.1 题目描述与输入输出模型力扣 239 的题面非常精炼给定一个整数数组 nums 和一个大小为 k 的滑动窗口窗口从数组的最左侧移动到最右侧每次只能看到窗口内的 k 个数字窗口每次向右移动一位要求返回滑动窗口中的最大值数组。举个例子。nums [1,3,-1,-3,5,3,6,7]k 3 时窗口依次是[1,3,-1] 最大值是 3[3,-1,-3] 最大值是 3[-1,-3,5] 最大值是 5[-3,5,3] 最大值是 5[5,3,6] 最大值是 6[3,6,7] 最大值是 7所以输出是 [3,3,5,5,6,7]。注意这里有几个关键点。窗口个数不是 n 个而是 n - k 1 个这个公式推导很容易理解第一个窗口覆盖下标 0 到 k-1之后窗口整体右移最后一个窗口覆盖下标 n-k 到 n-1所以窗口总数为 (n-1) - (k-1) 1 n - k 1。返回值是数组不是单个数。另外要注意题目没有说数组有序也没有说 k 一定小于 n。边界情况比如 k 1窗口里就一个元素滑动过程中最大值就是元素本身直接返回原数组即可k 等于 n 时整个数组只有一个窗口答案就是全数组的最大值。这些边界在写代码时都要照顾到否则很容易在测试用例上翻车。1.2 暴力解为什么能过用例却不能通用小白看到这道题第一反应往往是双重循环外层循环窗口起点内层循环对当前窗口做一次线性扫描求最大值。代码很好写def maxSlidingWindow_bruteforce(nums, k): n len(nums) if n 0 or k 0: return [] ans [] for i in range(n - k 1): cur_max nums[i] for j in range(i, i k): if nums[j] cur_max: cur_max nums[j] ans.append(cur_max) return ans时间复杂度是 O(nk)在数据量小的时候完全没问题。但如果 n 是 10 的 5 次方k 也是 10 的 5 次方这个算法就要跑约 10 的 10 次方次比较现代机器一秒钟也就跑几亿次这种量级直接超时。暴力解法的问题在于它没有利用“窗口滑动”时前后两个窗口之间的重叠关系。想象一下窗口从 [0, k-1] 滑到 [1, k]这两个窗口有 k-1 个元素是完全相同的只有左边出去一个、右边进来一个但我们把所有元素又重新扫了一遍这本身就是在浪费已经算过的东西。如果能把某个窗口的计算结果“带”到下一个窗口去就能省下大量重复劳动。这就是后续优化的核心出发点。暴力法也不是一无是处。写题时用它来和最优解对拍生成随机小规模数据验证结果完全一致是排除逻辑错误的利器。我在本地调试时经常保留这个函数作为“标准答案”后续所有优化版本都要跑一遍和它对拍这一招在算法题练习中特别实用。2. 核心思路单调队列为什么是这道题的最优解2.1 从“最大堆懒删除”说起在讲单调队列之前先看一条看起来似乎更自然的路径用大根堆维护窗口内的元素。堆顶就是最大值窗口每次右移时把新元素加入堆再把滑出窗口的元素删掉。这个思路可行但实现起来有一个让人头疼的细节——堆不能像数组那样按下标随机删除一个元素。标准做法叫“懒删除”先把元素和下标一起存进堆堆顶元素如果发现它的下标已经滑出窗口就把它弹掉直到堆顶是窗口内的元素为止。写成代码大概是import heapq def maxSlidingWindow_heap(nums, k): n len(nums) if n 0 or k 0: return [] pq [(-nums[i], i) for i in range(k)] heapq.heapify(pq) ans [-pq[0][0]] for i in range(k, n): heapq.heappush(pq, (-nums[i], i)) while pq[0][1] i - k: heapq.heappop(pq) ans.append(-pq[0][0]) return ans这个解法的时间复杂度是 O(n log k)因为每次堆操作都是 O(log k)n 个元素插入n 个元素可能被懒删除弹出总共是 O(n log k)。它能 AC 绝大多数数据规模但还不是最优。懒删除的实质是堆本身就包含了一些“已经过期但尚未被清除”的脏数据每次取堆顶前都要先清洗一遍。如果能做到窗口滑动时直接丢掉过期元素而不是等它堵在堆顶才处理那维护成本就更低了。这正好引出单调队列——它可以把这个复杂度进一步压到 O(n)。2.2 单调递减队列的完整设计单调队列和堆的本质区别在于堆只知道最大值在哪里却不关心非最大值元素之间的关系单调队列则更进一步它维护了一个“候选最大值”的名单名单里的元素按照值从大到小排列队头永远是当前窗口的最大值。具体维护规则有两条。第一条新元素入队前弹出队尾所有小于等于它的元素。为什么是所有小于等于它的元素因为新元素的下标比它们都大也就是说新元素在窗口中“活”的时间更长。如果新元素的值又比它们大或相等那么这些旧元素在接下来的任何一个窗口里都没机会成为最大值了留着它们只是浪费空间。把小于等于新元素的队尾全部弹掉相当于淘汰掉已经确定的“输家”。第二条窗口滑动后如果队头的下标已经滑出窗口弹出队头。这是因为队头虽然当前是最大值但它的“任期”已经结束了不能继续留在名单里。这两条规则配合起来队列里的元素始终维持两个特征按值递减、按下标递增。队头是最大值队尾是“最年轻”的候选者。每次查询最大值只取队头时间复杂度 O(1)。为什么叫单调队列而不是双端队列因为底层数据结构确实就是 C 里的 deque、Java 里的 Deque或者 Python 的 collections.deque。双端队列只是提供了头部和尾部都能 O(1) 增删的能力单调性是这个结构中我们主动维护的规则两者经常组合使用于是大家约定俗成叫它“单调队列”。2.3 为什么队列里存的是下标而不是值这是小白最容易卡住的地方我当年也被这个问题困扰了很久。直觉上队列里存值不是更直接吗每次取队头出来就是最大值多方便。但仔细一想就会发现隐患窗口滑动时我们得知道这个最大值是不是已经滑出窗口了而判断“是否还在窗口内”唯一可靠的依据就是下标。假设队列里只存值那在窗口从 [0, 2] 滑到 [1, 3] 时如果最大值恰好是下标 0 的元素我们只知道它的值是 5却不知道它是不是已经离开窗口。用值去判断过期根本做不到因为数组中可能有很多个 5你无法确定这个 5 到底属于谁。所以队列里存的一定是下标。取最大值时通过 nums[下标] 拿到值判断过期时直接用下标和窗口左边界比较一举两得。这个设计思路值得记住凡是涉及“按时间/位置淘汰元素”的数据结构优先考虑存下标而不是存值。后面做其他滑动窗口类题目时这个经验同样适用。3. 手把手实现从小白能跑的代码开始3.1 Python 参考实现与逐行解读先把完整的 Python 解法贴出来再逐行解释每个步骤的意图。from collections import deque def maxSlidingWindow(nums, k): n len(nums) if n 0 or k 0: return [] if k 1: return nums q deque() ans [] for i in range(n): # 第一步清理过期队头 while q and q[0] i - k: q.popleft() # 第二步弹出队尾所有小于等于当前值的下标 while q and nums[q[-1]] nums[i]: q.pop() # 第三步当前下标入队 q.append(i) # 第四步窗口成型后队头就是当前窗口最大值 if i k - 1: ans.append(nums[q[0]]) return ans先看清理过期队头的条件 q[0] i - k。当前窗口的范围是 [i-k1, i]如果队头下标小于等于 i-k说明它最迟出现在上一个窗口的末尾已经滑出当前窗口必须弹出。这里用一个 while 而不是 if是为了防止队头连续多个元素都过期的情况虽然理论上单调队列最多也就弹一两个但写成 while 逻辑更稳妥。再看弹出队尾的条件 nums[q[-1]] nums[i]。这里用的是小于等于也就是重复值时旧下标也让位给新下标。原因前面说过新下标“活得更久”让新下标入队能让队列更简洁同时不影响最大值结果。如果写成严格小于 相同值会同时存在多个也不会出错但队列会更长。这个细节放到第 5 节专门展开。最后是收集答案只有当 i k-1 时当前窗口才算完整队头下标对应的值才是窗口最大值追加到 ans。循环结束后 ans 的长度正好是 n - k 1。3.2 用一个完整用例手工模拟理论说一百遍不如亲手推一遍。继续用 nums [1,3,-1,-3,5,3,6,7]k 3 模拟整个过程。初始队列为空。i 0nums[0] 1。队列空不需要清理直接入队。队列下标 [0]对应值 [1]。窗口未满不收集结果。i 1nums[1] 3。队头 0 没有过期队尾 nums[0] 1 小于 3弹出。下标 1 入队。队列下标 [1]对应值 [3]。i 2nums[2] -1。队头 1 没有过期队尾 nums[1] 3 不小于 -1保留。下标 2 入队。队列下标 [1,2]对应值 [3,-1]。窗口完整队头 nums[1]3结果 [3]。i 3nums[3] -3。先检查队头 11 3-30 不成立不过期。队尾 nums[2]-1 不小于 -3保留。下标 3 入队。队列下标 [1,2,3]对应值 [3,-1,-3]。队头是 3结果 [3,3]。i 4nums[4] 5。先检查队头 11 1 成立说明下标 1 已经滑出窗口当前窗口为 [2,4]弹出。再看队头 22 1 不成立保留。接着从队尾开始弹nums[3]-3 小于 5弹出nums[2]-1 小于 5弹出队列现在只剩下标 1 已经被弹出实际为空。下标 4 入队。队列 [4]对应值 [5]。队头是 5结果 [3,3,5]。i 5nums[5] 3。队头 4 没有过期。队尾 nums[4]5 不小于 3保留。下标 5 入队。队列 [4,5]对应值 [5,3]。队头是 5结果 [3,3,5,5]。i 6nums[6] 6。队头 4 没有过期。队尾 nums[5]3 小于 6弹出队尾 nums[4]5 小于 6弹出。下标 6 入队。队列 [6]对应值 [6]。结果 [3,3,5,5,6]。i 7nums[7] 7。队头 6 没有过期。队尾 nums[6]6 小于 7弹出。下标 7 入队。队列 [7]对应值 [7]。结果 [3,3,5,5,6,7]。整个过程中每个下标最多入队一次、出队一次所以总操作次数是 O(n)均摊到每次窗口滑动就是 O(1)。这个手动推演过程非常值得自己拿纸笔做一遍比看十遍代码都更能理解单调队列到底在干什么。3.3 Java 版本与队列选型说明Java 的 LinkedList 实现了 Deque 接口很适合当双端队列用。注意用 ArrayDeque 性能更好但不允许存 null这道题存的是 Integer 下标不会出现 null可以安全使用。class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] ans new int[n - k 1]; DequeInteger q new ArrayDeque(); int idx 0; for (int i 0; i n; i) { while (!q.isEmpty() q.peekFirst() i - k) { q.pollFirst(); } while (!q.isEmpty() nums[q.peekLast()] nums[i]) { q.pollLast(); } q.offerLast(i); if (i k - 1) { ans[idx] nums[q.peekFirst()]; } } return ans; } }Java 版本和 Python 版本逻辑完全一致区别只在于语法。这里有一个编码习惯提醒出队时尽量显式调用 pollFirst / pollLast而不是混用 remove / poll因为 remove 在队列为空时会抛异常poll 返回 null在竞争场景下语义更安全。虽然算法题里不会出现并发问题但养成清晰的 API 使用习惯对日常工程协作有帮助。有些同学为了追求极速会用数组模拟双端队列类似 int[] q new int[n] 加上 head、tail 两个指针。这种写法在力扣上通常能快 1 到 2 毫秒但对小白来说优先保证逻辑清晰用内置双端队列完全足够 AC。优化这件事应该是理解和实现正确之后的锦上添花。4. 做完之后的扩展思考这类题的套路与变体4.1 复杂度对比暴力、堆、单调队列用一张表总结三种解法的取舍方便面试时快速回忆解法时间复杂度空间复杂度核心思想适合场景暴力扫描O(nk)O(1)对每个窗口重新求最大值数据量很小或验证用最大堆懒删除O(n log k)O(k)堆顶维护最大值过期再删能过大部分题但不够极致单调队列O(n)O(k)维护递减候选名单两头淘汰竞赛、面试最优解从表里能看出单调队列的均摊复杂度是最优的空间上没有额外开销只是用 O(k) 的空间存候选下标。这里要特别说明“均摊 O(n)”的含义不是每次循环只做常数步操作而是所有元素入队一次、出队一次的累计成本是 O(n)所以平均每次操作 O(1)。面试时把这个解释清楚往往比直接甩出复杂度结论更有说服力。4.2 几个值得练的同类变体题学会这道题之后可以顺手做几个变体巩固单调队列的思路。第一个变体是“滑动窗口最小值”。把代码里的弹出条件从“小于等于当前值”改成“大于等于当前值”维护递增队列队头就是最小值其余逻辑完全一致。第二个变体是“绝对差不超过限制的最长连续子数组”。这道题需要同时维护一个最大值队列和一个最小值队列窗口移动时如果当前窗口内的最大值和最小值之差超过限制就移动左边界并清理两个队列中过期的下标。这道题能很好地检验你对单调队列的掌控程度建议完成 239 之后下一周就刷它。第三个变体是“长度为 k 的子数组最大平均数”或者“大小为 k 且平均值最大的子数组”。这类题型本质是前缀和或定长滑动窗口不一定需要队列但能帮你区分“什么时候该用前缀和什么时候该用单调队列”。另外要提醒的是别把单调队列和单调栈搞混。单调栈解决的是“下一个更大元素”这类基于单侧扩展的问题比如柱状图中最大矩形单调队列解决的是“滑动窗口内最值”这类基于连续区间滑动的动态问题。两者都维护了单调性但单调栈通常只在一端进出而单调队列需要双端操作。区分它们的关键在于问题是“固定起点找下一个”还是“不断移动窗口找当前区间”。5. 常见问题与排查技巧实录5.1 队列存了值导致过期判断失效这是初学者最容易掉进去的坑也是最难通过样例排查看出来的问题。如果队列里只存值窗口滑动时你根本不知道怎么判断“队头的值是不是已经滑出窗口了”因为数组里多个位置可能存着相同的值光看数值分不清谁是谁。我自己第一次写这题时先把值存进队列然后试图用窗口左边界做标记结果写出了非常丑陋且容易出错的代码。后来才明白所有需要淘汰过期元素的数据结构题存下标都是更稳妥的设计。值是可以重复的下标是唯一的判断“是否过期”本质上是在判断位置而不是判断数值。如果你已经写了存值的代码对照测试用例 [5,4,3,2,1,6]k 3跑出错了也不用着急把队列内容打印出来看几个窗口很快就能发现问题。5.2 队列头过期忘了清结果错得莫名其妙还有一类常见错误是清理队头的时候用了 if 而不是 while或者把清理过期元素的步骤放在了入队之后。先说 while 和 if 的区别。虽然大部分情况下窗口滑动一步队头最多过期一个但也有可能队头过期的同时又因为新元素的加入、队尾弹出多个元素导致原本不在队头位置的元素突然变成了队头此时它也可能已经过期。用 if 只弹一次可能不够用 while 才是完备的。再说步骤顺序。正确顺序是先清理过期队头再弹出队尾较小值最后入队新下标。如果把“清理过期队头”放在最后就会出现在入队时队头还是过期元素导致后续弹出的比较结果失真。这个问题在小数据上也能发现调试时建议在每个循环结尾打印队列当前下标、对应值和已收集结果。5.3 用 还是 重复值处理的小细节弹出队尾元素时条件写成 nums[q[-1]] nums[i] 和 nums[q[-1]] nums[i] 都能通过所有测试用例但两者在重复值处理上有细微差别。用严格小于 当遇到重复最大值时旧下标会保留。例如窗口内两个 5队列可能同时存着旧 5 和新 5 的下标队头一直是旧 5直到旧 5 过期后新 5 顶上。这样不会出错但队列会多存几个元素逻辑上多了一些“其实没必要保留的候选者”。用小于等于 新元素入队时弹出的包括和它相等的旧元素相同值只保留最新下标。因为新下标在窗口中“存活时间”更长用新下标替代旧下标完全不会影响结果队列也更紧凑。在面试中把这个原因解释清楚会显得你对边界条件很有掌控力。我的建议是统一用 。它使队列始终保持“严格递减”的特性后续推演和讲解都更方便。5.4 边界条件与返回值类型最后是几个必须考虑进去的边界情况。当 nums 为空时直接返回空数组。当 k 为 0 时窗口大小为 0 没有意义也返回空数组。当 k 1 时每个窗口只有一个元素最大值就是它自己直接返回原数组即可不需要走队列逻辑。当 k n 时整个数组只有一个窗口答案就是数组的最大值。这个场景实际上已经退化成普通求最大值问题但单调队列代码也能正确处理因为没有元素会过期队列会退化成候选元素列表最后队头一定是全局最大值。返回值类型也要注意。力扣中这道题要求返回 int[]但有些平台可能要求 List 。如果你用 Python 刷题返回列表自然是最方便的如果用 Java注意提前初始化长度 n-k1 的数组否则 ArrayList 转 int[] 会多一层开销和麻烦。5.5 调试单调队列的通用技巧这里分享一个我常用的排查套路。先在本地写好一个确定正确的暴力版本然后写一个随机数据生成器生成长度 1 到 200 的随机整数数组和随机 k把暴力版本和单调队列版本的结果进行比对。一旦不一致把数组、k、两个输出全部打印出来然后手动模拟队列过程通常很快就能定位到是清理过期还是弹出条件写错了。另一个技巧是“打印队列状态”。在循环里把 i、当前值、队列下标、队列下标对应值、结果数组都打印出来例如i4 value5 queue[2,3] values[-1,-3] result[3,3]这个输出能直观地看到队头是否符合预期也能在面试现场帮你快速解释思路。很多人觉得自己看懂了单调队列但一到手写时还是会在边界条件上出错根源就在于没有形成“一边模拟一边验证”的习惯。最后再分享一点个人体会。我最早刷这道题的时候同样被下标、过期、递减这些概念绕得晕头转向后来是在纸上把例子完整推了一遍才真正理解单调队列的价值它本质上是在维护一个“按值排序、按时间淘汰”的候选人名单每个元素入队一次、出队一次所以高效。但如果你连暴力版本都没写过连窗口是怎么移动的都不清楚直接去背单调队列模板大概率很快就会忘光。我的建议是先老老实实写暴力再用数据规模倒逼自己思考优化最后再回到这道题把单调队列推演一遍把步骤吃透。这样来回两三轮滑动窗口最大值这类题目就不再是难题了。