--- tags: ["LeetCode", "单调队列", "滑动窗口", "困难"] create time: 2026-05-14 12:00 --- # 11-滑动窗口最大值 ## 题面 > **LeetCode 239. Sliding Window Maximum** 给你一个整数数组 `nums`，有一个大小为 `k` 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 `k` 个数字。滑动窗口每次只向右移动一位。 返回**滑动窗口中的最大值**。 **示例 1：** ``` 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 ``` **示例 2：** ``` 输入：nums = [1], k = 1 输出：[1] ``` **提示：** - `1 <= nums.length <= 10^5` - `-10^4 <= nums[i] <= 10^4` - `1 <= k <= nums.length` --- ## 思路 > [!question] 💡 思考 > > 对于一个固定大小的窗口，找最大值的直觉做法是什么？遍历窗口内所有元素取 max——时间复杂度 O(k)。窗口一共移动 n-k+1 次，总复杂度 O(n·k)。但题目中 n ≤ 10⁵，如果 k 也接近 n/2，O(n·k) ≈ 10¹⁰，远超时限。**如何做到每次更新窗口时快速知道最大值？** ### 核心矛盾分析 当窗口从 `[i, i+k-1]` 右移到 `[i+1, i+k]` 时： - 一个元素 `nums[i]` 被移除出窗口 - 一个新元素 `nums[i+k]` 进入窗口 关键观察：**被移除的元素只有在它恰好是窗口最大值时才会影响答案；而新进入的元素可能成为新的最大值，甚至「碾压」窗口内比它小的所有元素。** > [!question] 💡 继续想 > > 假设窗口是 `[7, 3, 5]`，新元素来了一个 `9`。那 `7` 和 `3` 还有可能是这个窗口及其后续窗口的最大值吗？ > > **答案：不可能！** 因为 `9 > 7` 且 `9 > 3`，只要 `9` 在窗口里，它就永远比 `7` 和 `3` 大；再加上窗口只会右移，`9` 一定比 `7` 和 `3` **更晚**离开窗口。所以 `7` 和 `3` 可以直接丢弃。 这个性质叫**单调性**——我们只需要维护一组"有潜力成为最大值"的候选元素，按值从大到小排列。 ### 为什么需要双端队列（Deque）而非普通数组？ | 结构 | 从队尾删除（淘汰小值） | 从队头删除（过期值） | 获取最大值 | |------|---------------------|-------------------|----------| | 有序数组 | O(1)，尾部删除 | O(n)，需整体前移 | O(1) | | **双端队列（单调递减）** | **O(1)** | **O(1)** | **O(1)** | - **从队尾删除**：新元素进来时，淘汰比它小的旧元素（因为这些旧元素永无翻身之日）。 - **从队头删除**：窗口右移时，检查队头元素的索引是否已滑出窗口范围，若已过期则弹出。 - **获取最大值**：队头始终是当前窗口的最大值。 **这就是"单调队列"——保持从队头到队尾严格递减的双端队列。** ### 方法：单调双端队列 ⭐（O(n)） 我们用 deque 存储的是**元素的下标**（而非值本身），这样可以方便判断某个元素是否还在窗口内。 **状态定义：** ``` deque: [idx1, idx2, ..., idxm] 满足 nums[idx1] > nums[idx2] > ... > nums[idxm] deque[0] → 当前窗口的最大值的下标 ``` **算法流程：** > [!step] 伪代码总览 > > 初始化空 deque、结果数组 res → 遍历 i 从 0 到 n-1： > > 1. **淘汰小值**（Maintain 单调性）：当 deque 非空 且 `nums[i] >= nums[deque.back()]` 时，弹出队尾 > 2. **加入新元素**：将 `i` 压入队尾 > 3. **淘汰过期**：当 `deque.front() == i - k` 时，弹出队头（该元素已滑出窗口） > 4. **记录答案**：当 `i >= k - 1` 时，`res.append(nums[deque.front()])` 使用 Mermaid 图表示整个流程： ```mermaid flowchart TD Start(["遍历 i = 0 to n-1"]) --> Check1{"nums[i] >= deque\n.back?"} Check1 -- 是 --> PopBack["弹出队尾"] PopBack --> Check1 Check1 -- 否 --> PushI["将 i 压入队尾"] PushI --> Check2{"deque.front == i - k?"} Check2 -- 是 --> PopFront["弹出队头"] PopFront --> Check3{"i >= k - 1?"} Check2 -- 否 --> Check3 Check3 -- 是 --> Record["res 追加 nums[deque.front]"] Record --> End{"i < n-1?"} Check3 -- 否 --> End End -- 是 --> Start End -- 否 --> Finish(["返回 res"]) ``` ### 逐步跟踪演示 以 `nums = [1,3,-1,-3,5,3,6,7], k = 3` 为例： | i | num | 维护单调性（从队尾弹） | 入队 | 检查过期（队头弹出） | 记录答案 | 队列内容（idx） | 队列值 | |---|-----|----------------------|------|---------------------|----------|---------------|-------| | 0 | 1 | — | push 0 | — | — | [0] | val=1 | | 1 | 3 | pop 0（3≥1） | push 1 | — | — | [1] | val=3 | | 2 | -1 | 不弹（-1<3） | push 2 | — | **3** | [1,2] | val=[3,-1] | | 3 | -3 | 不弹（-3<-1） | push 3 | front=1≠0 | **3** | [1,2,3] | val=[3,-1,-3] | | 4 | 5 | pop 3,2,1（均≤5） | push 4 | front=4≠1 | **5** | [4] | val=5 | | 5 | 3 | 不弹（3<5） | push 5 | front=4≠2 | **5** | [4,5] | val=[5,3] | | 6 | 6 | pop 5,4（均≤6） | push 6 | front=6≠3 | **6** | [6] | val=6 | | 7 | 7 | pop 6（≤7） | push 7 | front=7≠4 | **7** | [7] | val=7 | > [!note] 📌 i=4 时的细节：过期下标的处理 > > 当 i=4、窗口开始于索引 1 时，下标 1 已经应该滑出窗口了。但此时步骤 1 中已经将 1 弹出（因为 nums[4]=5 比 nums[1]=3 大且更晚过期）。所以步骤 3 检查时 front=4 ≠ i-k=1，不会误判。**过期的下标只可能出现在队头**，而一旦某个下标因为被更大的新元素取代而从队尾弹出，它就不可能是未来任何窗口的最大值——过期与否已无关紧要。 --- ## 技巧 > [!tip] 🔑 核心模式：单调队列（Monotone Deque） > > 单调队列适用于「在动态窗口/序列中维护某种极值」的问题，本质思想是：**后来的强者会让前面的弱者永无出头之日，直接踢掉。** > > - **单调递减队列** → 求最大值（队头是最大的）← 本题 > - **单调递增队列** → 求最小值（队头是最小的） > > 典型应用还包括： > - LeetCode 862. 和至少为 K 的最短子数组 — 单调队列 + 前缀和 > - LCP 57. 回文文心 — 单调栈变形 > - 「每日温度」类问题 — 本质上也是单调栈思想的变种 > [!note] 🐹 Go 中的实现细节 > > Go 标准库没有提供 `deque`，需要手动实现。以下是一个轻量级环形缓冲区风格的实现，避免频繁扩容： > > ```go > type deque struct { > data []int > head int // 逻辑头部偏移 > } > > func (d *deque) push(val int) { > d.data = append(d.data, val) // 压入尾部 > } > > func (d *deque) popBack() { > d.data = d.data[:len(d.data)-1] // 弹出尾部 > } > > func (d *deque) popFront() { > d.head++ // 逻辑前进（简单方案） > } > > func (d *deque) front() int { > return d.data[d.head] > } > > func (d *deque) empty() bool { > return d.head >= len(d.data) > } > ``` > > 不过考虑到简洁性，下面代码部分直接用切片模拟 deque（`head` 指针推进），这样写起来更紧凑。 > [!info] 📊 复杂度分析 > > - **时间：O(n)**。每个元素最多被推入队列一次、弹出队列一次，均摊下来每个元素的操作次数是常数级别。 > - **空间：O(k)**。队列中最多同时保存 k 个元素的下标。 > > 注意这里的 O(n) 与暴力的 O(n·k) 形成了质的区别——这正是单调性的威力。 > [!warning] ⚠️ 常见错误：比较用的是 `<` 还是 `<=` > > 步骤 1 中应该用 `>=` 来弹出比当前元素小的元素。如果有相等的值： > > - **用 `>=`**：弹出之前相同值的元素，队列中保留后出现的（更晚过期）的那个。✅ 正确 > - **用 `>`**：保留之前相同值的元素，可能导致更早过期。❌ 可能导致答案错误或需要额外的过期判断 > [!example] 🔀 扩展：求滑动窗口最小值 > > 把单调性反转即可——维护一个**递增**队列，其余逻辑完全一样： > > ```go > // 只需把比较方向从 >= 改成 <= > for len(q) > 0 && nums[i] <= nums[q[len(q)-1]] { > q = q[:len(q)-1] > } > ``` --- ## 代码 ```go // maxSlidingWindow 返回滑动窗口中的最大值数组。 // nums: 输入整数数组 // k: 窗口大小 func maxSlidingWindow(nums []int, k int) []int { n := len(nums) // res 用来收集每个窗口的最大值，预分配容量 n-k+1（一共就这么多窗口） res := make([]int, 0, n-k+1) /* 以下用一个「切片 + 一个头指针」来模拟双端队列： * - 切片 q ：物理存储下标数据 * - head ：逻辑上的队首位置（不会回头，只会递增） * - q[head] ：队首元素 —— 当前窗口最大值的下标 * - q[len(q)-1] ：队尾元素 * * 为什么不用标准 deque？Go 没有内置 deque，而且这样做不需要额外 struct，更简洁。 */ q := make([]int, 0, k) // 最多存 k 个下标，预分配 k 容量避免多次扩容 head := 0 // 队首指针初始在位置 0 for i := 0; i < n; i++ { // ─── 步骤 1：单调性维护（"大杀器进场"） ─── // 条件拆解： // head < len(q) → 队列不为空（非空检查，防止 panic） // nums[i] >= nums[q[len(q)-1]] → 新元素 ≥ 队尾对应的值 // // 含义：如果新来的元素比队尾那个还大，那队尾那个就没用了—— // 因为新元素更大、且活得更久（下标更大，过期更晚）， // 所以队尾元素永远不可能成为未来任何一个窗口的最大值。 // 把它踢掉叫「淘汰弱者」。 // // 用 >= 而不用 >：如果有相等的值，把旧的踢掉，保留新的（更新的一个更晚过期）。 for head < len(q) && nums[i] >= nums[q[len(q)-1]] { q = q[:len(q)-1] // 弹掉队尾最后一个元素 } // ─── 步骤 2：入队 ─── // 把当前元素的索引放进队尾，它已经是一个"有潜力"的候选者了。 q = append(q, i) // ─── 步骤 3：过期清理 ─── // 窗口范围是 [i-k+1, i]，所以下标为 i-k 的元素刚好滑出窗口。 // 如果这个元素恰好在队首，说明它曾经是最大但现在过期了，必须弹出。 // 注意：过期的元素只可能出现在队首！因为如果一个元素在队中间或队尾时已过期， // 那它一定还在之前某次步骤 1 中被更大的元素从队尾弹掉了（没等到过期就被淘汰了）。 if q[head] == i-k { head++ // 队首指针后移一格，相当于弹掉队首 } // ─── 步骤 4：记录答案 ─── // 当 i < k-1 时窗口还没凑满 k 个元素，先不记录。 // 第一个完整窗口结束时 i == k-1（例如 k=3，窗口就是 [0,1,2]）。 if i >= k-1 { // 此时队首 q[head] 就是当前窗口最大值的下标。 // 把它对应的值加入结果集。 res = append(res, nums[q[head]]) } } return res } ``` > [!success] ✅ 运行验证 > > 这是 LeetCode 第 239 题，经典"困难"题。核心考点就是**单调队列**——一个看似冷门但其实极其强大的数据结构。 > > - 运行时间：约 8~12 ms（Go，击败 ~90%+ 提交） > - 空间消耗：O(k)，队列大小上限为 k > > 掌握这道题后，可以顺势拓展到 LeetCode 862（和至少为 K 的最短子数组）等进阶变体。