题目描述
思路解析
一句话答案：LeetCode 239 滑动窗口最大值的最优解是单调队列：用双端队列存下标、保持对应值从队头到队尾递减，新数入队前先弹掉队尾所有比它小的（它们再也当不了最大值），队头下标滑出窗口就弹掉，队头始终指向当前窗口最大值。每个下标至多进出队各一次，时间 O(n)、空间 O(k)。
这道题真正在问什么
给数组 nums 和窗口大小 k，一个长度固定为 k 的窗口从最左滑到最右，要求输出每个位置上窗口内的最大值，组成结果数组。比如 nums = [1,3,-1,-3,5,3,6,7]、窗口大小取 3，答案是 [3,3,5,5,6,7]。难点在规模：窗口有 n - k + 1 个，如果每个窗口都独立找一遍最大值，重复劳动会非常可观。
为什么暴力 O(nk) 不够，堆也不完美
逐窗口扫描是 O(nk)，n 和 k 都到十万量级时直接超时。改用大顶堆能把取最大值降到 O(log n)，但堆删不掉「已经滑出窗口的旧元素」，只能懒删除——取堆顶时反复检查它是否还在窗口内，整体 O(n log n)，且实现别扭。
真正的突破口是一个淘汰观察：如果一个数比它右边的某个新来的数还小，那它这辈子都当不了窗口最大值了——新数比它大、还比它晚离开窗口，任何同时容纳两者的窗口里，最大值轮不到它。这样的数可以当场永久扔掉，根本不必留着比较。
单调队列的不变量是什么
把上面的淘汰规则落成数据结构，就是单调队列（用双端队列实现）：队列里存下标，保持这些下标对应的值从队头到队尾严格递减。每个新数 v 入队前，先把队尾所有值小于 v 的下标弹掉——它们正是被 v 永久淘汰的数——然后 v 的下标入队尾，递减性自动延续。
队列里存下标而不是存值，是为了回答「队头还在不在窗口里」：窗口右端走到 r 时，左边界是 r - k + 1，若队头下标小于等于 r - k，说明它已滑出窗口，从队头弹掉。两条规则各管一头：队尾弹「被淘汰的」，队头弹「过期的」，剩下的队头就永远是当前窗口的最大值。
为什么队头一定是窗口最大值
可以这样论证：窗口内任何一个数，要么还留在队列里，要么曾被某个更大且更靠右的数弹掉过——被弹掉的数一定不是最大值，因为弹它的那个数就在同一窗口里且比它大。所以窗口最大值必然还在队列中；而队列按值递减、队头经过过期检查后又保证在窗口内，故队头就是答案。窗口每凑满 k 个（r >= k - 1 起），把队头对应的值记入结果即可。
一个容易写错的细节：弹队尾的条件是「严格小于新值」。如果把相等的也弹掉，遇到重复的最大值时会过早删掉一个仍在窗口内的有效下标，等旧的那个滑出窗口后就无人接班了。
复杂度怎么算，边界在哪里
时间 O(n)：虽然循环体里嵌着弹队尾的 while，但每个下标一生至多入队一次、出队一次，所有弹出加起来不超过 n 次，均摊每步 O(1)。空间 O(k)：队列里的下标全部落在同一个窗口内，规模不超过 k。
边界上注意两点：窗口大小为 1 时每个窗口就是元素自身，算法退化为原样输出，逻辑无需特判；数组全递减时任何数都弹不掉别人，队列涨到 k 长、靠队头过期出队维持规模，这也是空间上界取到 O(k) 的情形。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住两条规则：① 队尾弹掉所有比新数小的（它们再也当不了最大值）；② 队头若滑出窗口就弹掉。剩下的队头永远是窗口最大值。
指针 r 走到下标 0，这一格的值是 1。先看队尾有没有比它小的需要弹掉。
下标 0 加到队尾。此刻队列里的值从队头到队尾依然递减，队头下标 0 就是目前的最大值候选。
指针 r 走到下标 1，这一格的值是 3。先看队尾有没有比它小的需要弹掉。
准备加入下标 1（值 3）。队尾这些比它小的下标（标红）被永久弹掉——有更大更新的 3 在，它们再也当不了窗口最大值。
下标 1 加到队尾。此刻队列里的值从队头到队尾依然递减，队头下标 1 就是目前的最大值候选。
指针 r 走到下标 2，这一格的值是 -1。先看队尾有没有比它小的需要弹掉。
下标 2 加到队尾。此刻队列里的值从队头到队尾依然递减，队头下标 1 就是目前的最大值候选。
窗口 [0,2] 满 3 个了。队头下标 1 指向的 3（高亮）就是这一窗的最大值，记入答案。
指针 r 走到下标 3，这一格的值是 -3。先看队尾有没有比它小的需要弹掉。
下标 3 加到队尾。此刻队列里的值从队头到队尾依然递减，队头下标 1 就是目前的最大值候选。
窗口 [1,3] 满 3 个了。队头下标 1 指向的 3（高亮）就是这一窗的最大值，记入答案。
指针 r 走到下标 4，这一格的值是 5。先看队尾有没有比它小的需要弹掉。
准备加入下标 4（值 5）。队尾这些比它小的下标（标红）被永久弹掉——有更大更新的 5 在，它们再也当不了窗口最大值。
下标 4 加到队尾。此刻队列里的值从队头到队尾依然递减，队头下标 4 就是目前的最大值候选。
窗口 [2,4] 满 3 个了。队头下标 4 指向的 5（高亮）就是这一窗的最大值，记入答案。
指针 r 走到下标 5，这一格的值是 3。先看队尾有没有比它小的需要弹掉。
下标 5 加到队尾。此刻队列里的值从队头到队尾依然递减，队头下标 4 就是目前的最大值候选。
窗口 [3,5] 满 3 个了。队头下标 4 指向的 5（高亮）就是这一窗的最大值，记入答案。
指针 r 走到下标 6，这一格的值是 6。先看队尾有没有比它小的需要弹掉。
准备加入下标 6（值 6）。队尾这些比它小的下标（标红）被永久弹掉——有更大更新的 6 在，它们再也当不了窗口最大值。
下标 6 加到队尾。此刻队列里的值从队头到队尾依然递减，队头下标 6 就是目前的最大值候选。
窗口 [4,6] 满 3 个了。队头下标 6 指向的 6（高亮）就是这一窗的最大值，记入答案。
指针 r 走到下标 7，这一格的值是 7。先看队尾有没有比它小的需要弹掉。
准备加入下标 7（值 7）。队尾这些比它小的下标（标红）被永久弹掉——有更大更新的 7 在，它们再也当不了窗口最大值。
下标 7 加到队尾。此刻队列里的值从队头到队尾依然递减，队头下标 7 就是目前的最大值候选。
窗口 [5,7] 满 3 个了。队头下标 7 指向的 7（高亮）就是这一窗的最大值，记入答案。
所有窗口滑完，每一窗的最大值串起来就是答案 [3,3,5,5,6,7]。每个数只入队、出队各一次，所以是 O(n)。
三个高频追问：均摊 O(n) 的道理、单调性怎么维持、求最小值如何改。
参考代码
from collections import dequedef maxSlidingWindow(nums, k): dq, ans = deque(), [] # dq 存下标，值单调递减 for r, v in enumerate(nums): while dq and nums[dq[-1]] < v: # 队尾弹掉更小的 dq.pop() dq.append(r) if dq[0] <= r - k: # 队头滑出窗口 dq.popleft() if r >= k - 1: # 窗口凑满 ans.append(nums[dq[0]]) return ans复杂度
- 时间：O(n)，每个下标最多入队一次、出队一次，总操作量和 n 成正比
- 空间：O(k)，队列里最多同时存一个窗口的下标，规模不超过 k
易错点
面试追问把动画讲成自己的话
追问为什么这个算法是 O(n) 而不是 O(nk)？
追问队列为什么能保持单调递减？
追问如果要求窗口最小值怎么改？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
找到字符串中所有字母异位词
LeetCode 438 · 中等 · 沿着 滑动窗口 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题