LeetCode 239 滑动窗口最大值（Sliding Window Maximum）：从暴力扫描到单调队列的 O(n) 解法全解

LeetCode 239 滑动窗口最大值（Sliding Window Maximum）：从暴力扫描到单调队列的 O(n) 解法全解

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文以 hints/sliding-window-maximum.md 的提示线索为主线，结合仓库中 articles/sliding-window-maximum.md 的完整题解与 Python、Java、C++、Go、TypeScript 等多语言实现，系统讲解 LeetCode 239「滑动窗口最大值」的四种主流解法。读完本文，你将掌握从 O(n·k) 暴力法到 O(n) 单调队列的完整优化链路，理解堆的懒删除技巧，并能对照仓库源码写出可运行的答案。

题目与前置知识

给定整数数组nums和滑动窗口大小k，窗口每次向右移动一位，要求返回每个窗口中的最大值。以仓库 cpp/0239-sliding-window-maximum.cpp 注释中的经典示例为例：

nums = [1,3,-1,-3,5,3,6,7], k = 3 -> [3,3,5,5,6,7]

该题属于 NeetCode Roadmap 的Sliding Window分类（见 README.md 中 0239 一行的归类），需要先掌握以下基础：

• 滑动窗口（Sliding Window）：维护一个固定大小的窗口在数组上右移；
• 双端队列（Deque）：支持 O(1) 时间在两端插入/删除；
• 单调队列（Monotonic Queue）：队列内元素按值单调有序，用于范围最值查询；
• 堆/优先队列（Heap/Priority Queue）：配合懒删除快速取最值。

复杂度目标：为什么 O(n·k) 不够好

提示文档开篇给出的目标很明确（hints/sliding-window-maximum.md 的 Recommended Time & Space Complexity）：

你的解法应达到或优于O(n log n) 时间、O(n) 空间，其中 n 为数组长度。

这是一个关键约束信号：朴素的双重循环做法是 O(n·k)，当 k 接近 n 时会退化到 O(n²) 级别，无法通过大数据量用例。因此必须寻找能够在 O(1) 时间获取窗口当前最大值的数据结构，这正是后面堆与单调队列两条路线的出发点。

Hint 1：暴力法的瓶颈在哪

暴力解法是对每个窗口起点i（范围0到len(nums) - k），再扫描窗口内全部k个元素找最大值：

class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: output = [] for i in range(len(nums) - k + 1): maxi = nums[i] for j in range(i, i + k): maxi = max(maxi, nums[j]) output.append(maxi) return output

复杂度：时间 O(n·k)，额外空间 O(1)（输出数组另计 O(n - k + 1)）。

问题在于：相邻窗口有 k-1 个元素重叠，暴力法每次滑动都把这些重叠元素重新扫描一遍，造成大量重复计算。Hint 1 提示我们思考：能否用某种数据结构，让窗口的最大值在O(1) 时间内直接拿到？

Hint 2：用最大堆记录 (值, 下标)

处理"最大值/最小值"最自然的数据结构是堆：取堆顶最值只需 O(1)。此处应使用最大堆。

但这里有一个陷阱——堆中的元素会"过期"：窗口左移后，旧的最大值可能已经不在当前窗口内。Hint 2 的提示是：换一种入堆方式——不要把裸值入堆，而是把(value, index)二元组一起入堆，用下标来判断元素是否仍属于当前窗口。

以 Python 实现为例（见 articles/sliding-window-maximum.md Heap 一节）：

class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: heap = [] output = [] for i in range(len(nums)): heapq.heappush(heap, (-nums[i], i)) # Python 无原生最大堆，取负模拟 if i >= k - 1: while heap[0][1] <= i - k: # 下标过期的堆顶直接弹出 heapq.heappop(heap) output.append(-heap[0][0]) return output

仓库中其他语言的对应实现都遵循同一思路：

• Java：java/0239-sliding-window-maximum.java（Deque 版）
• C++：cpp/0239-sliding-window-maximum.cpp（priority_queue<pair<int,int>>）
• Go：go/0239-sliding-window-maximum.go（自定义MaxHeap [][2]int）
• Rust：rust/0239-sliding-window-maximum.rs（BinaryHeap<(i32, usize)>）

Hint 3 & Hint 4：堆的懒删除（Lazy Deletion）

窗口每滑动一步，都会有元素从左侧离开窗口，但它们仍留在堆里。Hint 3 提出的问题是：如何高效处理这种"幽灵元素"？

Hint 4 给出了答案：

只要堆顶最大值仍在当前窗口内，就可以忽略那些已过期但还留在堆里的元素；只有当最大值本身过期时，才不断弹出堆顶，直到堆顶属于当前窗口。

因为被过期元素挡在下面的有效元素，迟早会在它成为堆顶时被清理，因此不需要在滑动时逐一删除过期元素。这种"先留着、等到碍事再删"的手法就是经典的懒删除（lazy deletion）。

堆解法整体复杂度：时间 O(n log n)（每个元素入堆/出堆各一次），空间 O(n)。这正好满足提示文档给出的目标上界。

最优解：单调双端队列（Deque），O(n) 时间

如果说堆解法已经达标，那么单调队列则把时间进一步压到O(n)——这也是提示文档暗示的进阶方向。

核心思想：用双端队列只存下标，且队列中下标对应的值严格递减。由此保证：

1. 队首永远是当前窗口最大值的下标；
2. 新元素入队时，从队尾弹出所有值更小的下标——它们永远不可能成为未来窗口的最大值（它们被新元素"挡住"且更早过期），留着无用；
3. 若队首下标已滑出窗口（l > q[0]），从队首弹出。

以仓库 python/0239-sliding-window-maximum.py 的实现为范本：

class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: output = [] q = collections.deque() # 存下标 l = r = 0 while r < len(nums): # 弹出队尾所有值更小的下标（它们不可能成为最大值） while q and nums[q[-1]] < nums[r]: q.pop() q.append(r) # 队首若已滑出窗口则移除 if l > q[0]: q.popleft() # 窗口达到 k 时记录答案 if (r + 1) >= k: output.append(nums[q[0]]) l += 1 r += 1 return output

各语言的落地版本均可直接对照阅读：

• Java：java/0239-sliding-window-maximum.java（Deque<Integer>+for循环版，判断过期条件为q.peekFirst() < i - k + 1）
• C++：cpp/0239-sliding-window-maximum.cpp
• Go：go/0239-sliding-window-maximum.go
• TypeScript：typescript/0239-sliding-window-maximum.ts

复杂度：每个元素至多入队一次、出队一次，均摊O(n) 时间，O(n) 空间。这是本题的最优解法，也是面试中应优先给出的答案。

补充视角：线段树与分块预处理（O(n log n) / O(n)）

提示文档的主线是堆/队列，但完整题解 articles/sliding-window-maximum.md 还提供了两种值得了解的替代方案：

线段树（Segment Tree）：把区间最大值预处理进一棵线段树，每个内部节点存左右子区间最大值的较大者；随后对每个窗口[i, i + k - 1]做一次 O(log n) 的区间最值查询。整体时间 O(n log n)，空间 O(n)。构建时叶子放在数组后半段、内部节点自底向上取 max 的写法在题解中有完整 Python/Java/C++/Go/Rust 实现。

分块 DP（leftMax + rightMax）：把数组按块大小 k 切分，分别预处理每个块内从左到右（leftMax）和从右到左（rightMax）的前缀/后缀最大值。任一窗口[i, i+k-1]的最大值 =max(leftMax[i + k - 1], rightMax[i])，即每块窗口的左右两半各取自一个预处理数组。时间 O(n)、空间 O(n)，无需任何高级数据结构。

常见坑（Common Pitfalls）

根据题解末尾的总结，以及仓库各语言实现的对比，写代码时最容易踩的坑如下：

1. 队里存值不存下标：存值就无法判断元素是否已经滑出窗口。务必存下标，取值时用nums[index]。
2. 窗口边界判断错误：第一个合法窗口在right >= k - 1（等价于right + 1 >= k）时才出现，k与k-1差一会导致漏掉第一个窗口或过早记录结果。
3. 未维护单调递减：弹出条件写错（如用<=代替<）或忘记弹出，队首就不再是真实最大值。正确写法是while 队尾对应值 < 当前值: 弹出队尾。
4. 输出数组大小算错：窗口数量是n - k + 1，不是n或n - k；当k == n时结果恰好只有一个元素。
5. 线段树区间边界混淆：查询区间[i, i + k - 1]两端都含；搞混闭/开区间会多查或少查元素。

小结与仓库索引

回到提示文档的复杂度目标：O(n log n) 时间 / O(n) 空间。本文给出的两条达标路线是——最大堆 + 懒删除（O(n log n)），以及单调双端队列（O(n)，更优）。暴力法（O(n·k)）仅用于建立直觉。

如需在本地复现与练习，可直接查阅以下仓库文件：

• 提示线索：hints/sliding-window-maximum.md
• 完整图文题解（5 种解法 + 多语言代码）：articles/sliding-window-maximum.md
• 单调队列实现：Python python/0239-sliding-window-maximum.py、Java java/0239-sliding-window-maximum.java、C++ cpp/0239-sliding-window-maximum.cpp、Go go/0239-sliding-window-maximum.go、TypeScript typescript/0239-sliding-window-maximum.ts

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode