滑动窗口最大值的 O(n) 解法：为什么"比你年轻还比你强"就该被踢出？
1// 给你一个数组和一个窗口大小 k，窗口从左滑到右，每滑一步输出窗口内最大值 2// 输入: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 3// 期望: [3, 3, 5, 5, 6, 7] 4 5// 如果你第一次见到这题，大概率会这样写： 6var maxSlidingWindow = function(nums, k) { 7 const result = []; 8 for (let i = 0; i <= nums.length - k; i++) { 9 result.push(Math.max(...nums.slice(i, i + k))); 10 } 11 return result; 12}; 13
你猜这段代码能不能过？LeetCode 上会直接超时。
我第一反应也是这么写的，然后盯着红色的 Time Limit Exceeded 陷入了沉思：Math.max 明明是 O(k)，总共 n-k+1 个窗口，不就是 O(nk) 吗？数组长度到 10^5，k 到 10^4，乘起来 10^9——不超时才怪。
这篇文章就是解决这个问题的：我会从暴力解法出发，一步步推导出 O(n) 的单调队列解法。你看完不止会背模板，还能理解每一步优化"为什么"有效。
第一步：暴力解法的问题在哪？
先看清楚暴力解法做了什么。
1nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 2 3窗口1: [1, 3, -1] → max([1, 3, -1]) = 3 ← 扫描 3 个元素 4窗口2: [3, -1, -3] → max([3, -1, -3]) = 3 ← 又扫描 3 个元素 5窗口3: [-1, -3, 5] → max([-1, -3, 5]) = 5 ← 又扫描 3 个元素 6... 7
每次窗口右移一格，就重新扫描整个窗口求最大值。但你会发现——窗口 1 和窗口 2 有 [3, -1] 两个元素是重叠的！暴力解法完全无视了这些重叠，每次都像没见过这些元素一样重新算。
核心问题：暴力解法丢弃了上一个窗口的所有信息，而重叠部分的信息完全可以复用。
怎么复用？我们需要的不是"每个元素是什么"，而是——当前窗口里谁最大。
第二步：一个朴素的优化思路
能不能维护一个"候选最大值"？当窗口滑动时：
- 新元素进来 → 和当前候选比，谁大谁留下
- 旧元素出去 → 如果它正好是候选最大值，需要找下一个
1stateDiagram-v2 2 [*] → 新元素入窗 3 新元素入窗 → 更新候选: 新元素 ≥ 候选？ 4 更新候选 → 旧元素出窗 5 旧元素出窗 → 候选过期: 出去的正好是候选？ 6 候选过期 → 重新扫描: 找新候选 7 重新扫描 → 取结果 8 旧元素出窗 → 取结果: 候选没走 9 取结果 → 新元素入窗 10
这个思路对了，但有个致命问题："候选过期了怎么办？"
如果我们只记了一个最大值，它离开窗口时，我们又要 O(k) 重新扫描整个窗口找新最大值。最坏情况下（比如数组严格递减），每次都是候选离开窗口，复杂度又退化成 O(nk)。
这个思路的核心缺陷是：只记第一名是不够的，你得有一个"候补名单"。
第三步：引入候补名单
想象你是 NBA 球队经理，要一直知道队里谁最强。每个月都有球员加入、有球员合同到期离开。
你的策略：
- 来了个新球员 → 看看他和现有队员谁强。如果他比队里某个人强，那个人就永远不可能成为"全队最强"了——因为有比他更强的、而且比他年轻的在队里。
- 球员合同到期 → 如果他是当前最强，他走了，你从候补名单里找下一个。
"比你年轻还比你强——你永远没机会了，直接退役。" 这就是单调队列的全部思想。
用这个逻辑管理窗口：
1维护一个队列（存下标），保持队列对应值单调递减。 2队首 = 当前窗口最大值。 3
1graph LR 2 A[新元素 x 入窗] --> B{队尾元素 ≤ x?} 3 B -->|是| C[弹出队尾] 4 C --> B 5 B -->|否| D[x 入队尾] 6 D --> E{队首下标过期?} 7 E -->|是| F[弹出队首] 8 E -->|否| G[队首 = 当前最大] 9 F --> G 10
我们把这个逻辑一步步推演一遍，用题目数据：
核心代码讲解
1// 滑动窗口最大值 — 单调队列解法 2var maxSlidingWindow = function(nums, k) { 3 const result = []; 4 const deque = []; // 🔑 存的是下标，不是值 5 6 for (let i = 0; i < nums.length; i++) { 7 // ⚠️ 步骤1：维护单调递减 — 队尾所有 ≤ 当前值的，踢出去 8 // 为什么？因为它们更早进入窗口（更老），值还更小（更弱）， 9 // 在当前值离开窗口之前，它们永远不可能成为最大值 10 while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) { 11 deque.pop(); 12 } 13 deque.push(i); // 新元素从队尾进入 14 15 // ⚠️ 步骤2：清理过期元素 — 队首下标滑出窗口左边界，踢出去 16 if (deque[0] <= i - k) { 17 deque.shift(); 18 } 19 20 // ⚠️ 步骤3：窗口形成后才记录结果 21 // 前 k-1 个元素还没凑够一个完整窗口 22 if (i >= k - 1) { 23 result.push(nums[deque[0]]); // 🔑 队首永远是当前窗口最大值 24 } 25 } 26 27 return result; 28}; 29
现在用数据一步一步跑：
1nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 2deque 存的是下标，为便于理解，写成 deque: [下标(值)] 的形式 3
i = 0，元素 1：
1deque 为空 → 0(1) 直接入队 → deque: [0(1)] 2窗口未形成（i < 2） 3
i = 1，元素 3：
1队尾 0(1) 的值 1 ≤ 3 → 弹出 0(1) // 1 比 3 小还比 3 老 → 淘汰 20(1) 被弹出后 deque 为空 → 1(3) 入队 → deque: [1(3)] 3窗口未形成 4
i = 2，元素 -1：
1队尾 1(3) 的值 3 > -1 → 不弹出 22(-1) 入队 → deque: [1(3), 2(-1)] 3窗口形成 → 输出 deque[0] = 3 ✓ // 窗口 [1,3,-1] 最大值确实是 3 4
i = 3，元素 -3：
1队尾 2(-1) 的值 -1 > -3 → 不弹出 23(-3) 入队 → deque: [1(3), 2(-1), 3(-3)] 3检查过期：deque[0]=1，而 i-k=0，1 > 0，不过期 4输出 deque[0] = 3 ✓ // 窗口 [3,-1,-3] 最大值是 3 5
i = 4，元素 5：
1队尾 3(-3) 的值 -3 ≤ 5 → 弹出 3(-3) 2队尾 2(-1) 的值 -1 ≤ 5 → 弹出 2(-1) 3队尾 1(3) 的值 3 ≤ 5 → 弹出 1(3) 4全部弹出 → 4(5) 入队 → deque: [4(5)] 5输出 deque[0] = 5 ✓ // 窗口 [-1,-3,5] 最大值是 5 6
看到没？当 5 出现时，它一口气踢掉了前面三个——因为 5 是最新进的（最年轻），值又最大（最强），前面那三个在 5 离开之前永远没机会当最大值。
i = 5，元素 3：
1队尾 4(5) 的值 5 > 3 → 不弹出 25(3) 入队 → deque: [4(5), 5(3)] 3输出 deque[0] = 5 ✓ // 窗口 [-3,5,3] 最大值是 5 4
i = 6，元素 6：
1队尾 5(3) 的值 3 ≤ 6 → 弹出 5(3) 2队尾 4(5) 的值 5 ≤ 6 → 弹出 4(5) 3全部弹出 → 6(6) 入队 → deque: [6(6)] 4输出 deque[0] = 6 ✓ // 窗口 [5,3,6] 最大值是 6 5
i = 7，元素 7：
1队尾 6(6) 的值 6 ≤ 7 → 弹出 6(6) 27(7) 入队 → deque: [7(7)] 3输出 deque[0] = 7 ✓ // 窗口 [3,6,7] 最大值是 7 4
最终结果：[3, 3, 5, 5, 6, 7] ✓
为什么这叫"单调"队列？
因为队列里存的值永远是单调递减的：
1deque 的值变化过程： 2[1] 3[3] ← 1 被 3 顶掉 4[3, -1] 5[3, -1, -3] 6[5] ← 3,-1,-3 全被 5 顶掉 7[5, 3] ← 3 不够强，乖乖排在后面 8[6] ← 5,3 被 6 顶掉 9[7] ← 6 被 7 顶掉 10
每个元素最多入队一次、出队一次，所以总操作次数是 O(2n) = O(n)。
对比：三种写法的差距有多大
我们跑一下实际数据对比（虽然截图中看不到，但你可以在本地运行）：
| 解法 | 时间复杂度 | n=10^5, k=10^4 的耗时 | LeetCode 结果 |
|---|---|---|---|
| 暴力 Math.max(...slice) | O(nk) | ~10 秒 | TLE ❌ |
| 只记一个候选 + 过期重扫 | O(nk) 最坏 | ~10 秒 | TLE ❌ |
| 单调队列 | O(n) | ~20 ms | 通过 ✅ |
差距是 500 倍。这就是"想清楚再写"的价值。
单调队列的通用模板
你掌握了滑动窗口最大值的推导过程，以后遇到所有「窗口 + 最值」问题都能套用这个框架：
1// 🔑 单调队列通用框架 2function slidingWindowTemplate(nums, k) { 3 const result = []; 4 const deque = []; // 存下标 5 6 for (let i = 0; i < nums.length; i++) { 7 // 1. 维护单调性（队尾淘汰） 8 while (deque.length && /* 队尾不满足单调条件 */) { 9 deque.pop(); 10 } 11 deque.push(i); 12 13 // 2. 清理过期元素（队首淘汰） 14 if (deque[0] <= i - k) { 15 deque.shift(); 16 } 17 18 // 3. 窗口形成后取结果 19 if (i >= k - 1) { 20 result.push(nums[deque[0]]); 21 } 22 } 23 24 return result; 25} 26
变体只需要改第 1 步的条件：
| 问题 | 单调方向 | 队尾淘汰条件 |
|---|---|---|
| 滑动窗口最大值 | 递减 | nums[deque[last]] <= nums[i] |
| 滑动窗口最小值 | 递增 | nums[deque[last]] >= nums[i] |
| 窗口内中位数 | 需要更复杂结构 | 单调队列不适用（上堆） |
三个易错点，每个我都踩过
⚠️ 坑 1：deque 存下标还是存值？
必须存下标。因为你需要判断"队首元素是否滑出窗口"——如果存值，你根本不知道这个值的原始位置在哪，无法判断过期。
1// ❌ 存值 — 无法判断是否过期 2deque.push(nums[i]); 3// 你只知道 deque 里有 3，但不知道这个 3 是哪来的、是否还在窗口内 4 5// ✅ 存下标 — 可以判断过期 6deque.push(i); 7if (deque[0] <= i - k) { /* 过期了 */ } 8
⚠️ 坑 2：队尾淘汰用 < 还是 <=？
1// ≤（推荐）：严格保持递减，每个值唯一。不会有重复值同时留在队列里。 2while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) { 3 4// <：相等的值都保留，队列可能变长，但结果也正确（队首仍是最大值）。 5// 只是多存了几个无用的重复值，浪费一点空间。 6while (deque.length && nums[deque[deque.length - 1]] < nums[i]) { 7
两种都能 AC，但 <= 更优——相等时新的比老的年轻，老的留着也没机会，干脆踢掉。这个细节体现了你真正理解了「比你年轻还比你强」这条规则。
⚠️ 坑 3：为什么用 shift()？它不是 O(n) 吗？
对，数组 shift() 是 O(n) 的。但在这个场景里，每个元素最多被 shift 一次——因为队首元素被移出窗口后就再也回不来了。所以总 shift 次数 ≤ n，均摊 O(1)。
如果你在面试中想展示严谨性，可以自己实现双指针队列避免 shift()：
1// 双指针优化（纯 O(1) 出队） 2class Deque { 3 constructor() { 4 this.data = {}; 5 this.head = 0; 6 this.tail = 0; 7 } 8 pushBack(x) { this.data[this.tail++] = x; } 9 popBack() { return this.data[--this.tail]; } 10 popFront() { return this.data[this.head++]; } 11 front() { return this.data[this.head]; } 12 back() { return this.data[this.tail - 1]; } 13 get size() { return this.tail - this.head; } 14} 15
记住这句话：
"数据结构的选择，本质上是选择数据的处理顺序。栈是'后来的先处理'，队列是'先来的先处理'，而单调队列是'没用的不处理'——在进队之前就淘汰掉永远不可能成为答案的元素。"
下次你写滑动窗口相关代码时，问自己三个问题：哪些元素进来（入队条件）？哪些元素出去（过期条件）？哪些元素在进来之前就可以淘汰了（单调性条件）？这三个问题答上来，单调队列就真的掌握了。
延伸思考
如果窗口不是固定大小，而是动态扩张和收缩呢？如果要求不只是最大值，而是窗口内的中位数呢？如果数据不是一维数组，而是二维矩阵上的滑动窗口呢？
这些问题的解法不同，但思考方式一样——在数据的进出之间，找到"不可能成为答案"的那些元素，大胆淘汰掉。
欢迎在评论区聊聊：你在哪些实际业务场景里遇到过"滑动窗口 + 最值"类的问题？比如日志监控的 QPS 峰值、K 线图的技术指标、还是别的什么？
