高频必考！滑动窗口最大值：单调队列如何把 O(nk) 优化到 O(n)？

LeetCode 239「滑动窗口最大值」是Hard难度的经典题也是各大厂面试的高频题。给你一个数组和窗口大小k窗口每滑一步就要立刻知道窗口内的最大值。暴力每个窗口遍历一遍 → O(nk)n1e5 时直接炸大顶堆取最大值O(log k)但删除“离开窗口”的元素很麻烦得懒删除 堆顶清理代码复杂且易错单调队列每个元素入队出队各一次O(n) 搞定而且代码干净利落现在不只给你能AC的代码更给你一套“单调递减双端队列”的通用框架。以后遇到“滑动窗口最值”类问题你都能用同样的套路——队尾弹小队首弹旧队首即答案。 题目速览30 秒读懂给定数组nums和窗口大小k窗口从左向右滑动返回每个窗口的最大值。示例nums [1,3,-1,-3,5,3,6,7],k3输出[3,3,5,5,6,7]约束n ≤ 1e5暴力 O(nk) 必挂。 核心思路用单调递减队列“淘汰”永远不可能成为最大值的元素暴力到底慢在哪里每个窗口独立求最大值完全不利用上一个窗口的信息。窗口每次只变一个元素出去一个进来一个但暴力把所有 k 个元素重新扫一遍。关键观察单调性的威力假设窗口内有两个元素nums[i]和nums[j]且i jj 在 i 右边。如果nums[i] nums[j]那么nums[i]永远不可能成为任何后续窗口的最大值——因为nums[j]比它大而且nums[j]会留在窗口中比nums[i]更久。所以我们可以维护一个单调递减的队列存索引从队尾入队时把所有比新元素小的旧元素全部弹出它们已无价值从队首取最大值前检查队首是否已经滑出窗口过期则弹出队首永远是当前窗口的最大值每个元素最多入队一次、出队一次总操作O(2n)均摊O(1)。️ 图解全过程手把手走一遍nums [1, 3, -1, -3, 5, 3, 6, 7],k3队列存索引i新元素操作队尾弹出小的队首弹出过期的队列索引→值窗口范围最大值01入队[0→1]未满—1313弹出0入队1[1→3]未满—2-1入队[1→3, 2→-1][0,2]33-3入队[1→3,2→-1,3→-3][1,3]345弹出3(-3)、2(-1)、1(3)入队4[4→5][2,4]553入队[4→5, 5→3][3,5]566弹出5(3)、4(5)入队6[6→6][4,6]677弹出6(6)入队7[7→7][5,7]7注意i3 时队首索引1仍有效1 ≥ 3-311所以未过期。关键点新元素5入队时把前面所有比它小的3,-1,-3全部弹出因为它们再也不可能当最大值了。队列始终保持从队首到队尾严格递减。 代码实现Python 版fromcollectionsimportdequeclassSolution:defmaxSlidingWindow(self, nums: List[int], k: int)- List[int]:dq deque()# 存索引队首→队尾 递减ans []fori, valinenumerate(nums):# 1. 队首过期索引 i-k1 的弹出whiledqanddq[0] i - k 1:dq.popleft()# 2. 队尾维护弹出所有比当前值小的元素whiledqandnums[dq[-1]] val:dq.pop()# 3. 当前索引入队dq.append(i)# 4. 当窗口满时队首即为最大值ifi k -1:ans.append(nums[dq[0]])returnansJava 版classSolution{publicint[] maxSlidingWindow(int[] nums,intk) {DequeInteger dq newArrayDeque();// 存索引int[] ans newint[nums.length - k 1];intidx 0;for(inti 0; i nums.length; i) {// 1. 弹出过期队首while(!dq.isEmpty() dq.peekFirst() i - k 1) {dq.pollFirst();}// 2. 弹出队尾小于当前值的元素while(!dq.isEmpty() nums[dq.peekLast()] nums[i]) {dq.pollLast();}// 3. 入队dq.offerLast(i);// 4. 取结果if(i k -1) {ans[idx] nums[dq.peekFirst()];}}returnans;}}⚠️致命坑必看队列里存的是索引不是值这样才能判断过期dq[0] i-k1。两个 while 的顺序先弹过期队首再弹队尾小元素最后入队。顺序不能乱。比较时用还是一般用相等时保留旧元素不影响正确性且减少操作。⏱️ 复杂度分析面试必问时间每个元素最多入队一次、出队一次总操作O(2n)均摊O(1) →O(n)空间双端队列最多存k个元素 →O(k)不计返回结果 举一反三4 道高频变种题一套框架通吃题目差异点应对策略LeetCode 1438. 绝对差不超过限制的最长连续子数组需要同时维护最大值和最小值用两个单调队列一个递减、一个递增窗口内max-min超限时移动左边界LeetCode 862. 和至少为K的最短子数组前缀和 单调队列递增队列存前缀和索引维护单调递增以找到满足条件的最短子数组LeetCode 1499. 满足不等式的最大值二维坐标 单调队列优化维护队列中y - x的单调递减结合滑动窗口LeetCode 1696. 跳跃游戏 VI跳跃得分最大化单调队列维护前k步内的最大得分O(n)动态规划优化 面试追问模拟提前准备惊艳全场Q1为什么不用优先队列大顶堆优先队列取最大值O(log k)但删除“离开窗口”的元素很麻烦堆不支持任意位置删除只能“懒删除” —— 在堆顶检查元素是否过期过期则弹出。这样每次可能弹掉多个过期元素摊还也是O(nlogk)。而单调队列直接利用单调性队首就是最大值过期队首也在队首删除O(1)总O(n)。性能更优代码也更简洁。Q2队列里存索引而不存值为什么因为需要知道每个元素在数组中的位置才能判断它是否已经滑出窗口即index i-k1。如果只存值无法判断过期。存索引后通过nums[dq[0]]取值即可。Q3如果窗口需要同时取最大值和最小值怎么做维护两个双端队列一个单调递减队首最大一个单调递增队首最小。在每次滑动时分别维护两个队列然后可以同时得到最大值和最小值。LC.1438 就是这种场景。Q4单调队列和单调栈有什么区别维度单调队列单调栈数据结构双端队列两端操作栈一端操作出队/出栈条件队首按窗口过期弹出栈顶按遍历结束弹出典型应用滑动窗口最值下一个更大/更小元素元素进出次数每个最多一次每个最多一次 实战小技巧刷题党必备口诀队尾弹小保持递减队首弹旧窗口过期队首即答案。模板凡是“滑动窗口内求最值”类问题优先想到单调队列。调试打印队列内索引和对应值观察是否严格递减。边界k1时每个窗口只有自身单调队列也适用kn时只有一个窗口队首即为全局最大值。 实际应用场景不止是刷题量化交易滑动时间窗口内找股票最高价/最低价网络监控实时统计最近 N 秒内的流量峰值图像处理滑动窗口最大值滤波形态学膨胀操作日志分析滚动时间窗口内检测异常峰值游戏排行榜统计每个时间段内的最高分 今日思考题如果把题目改为“滑动窗口最小值”代码需要改几行只需将nums[dq[-1]] val改为即保持单调递增其他完全相同。如果同时求最大和最小你能写出维护两个队列的框架吗