LeetCode 239. 滑动窗口最大值（详细技术解析）

#本文针对 LeetCode 239. 滑动窗口最大值 问题，提供完整的解题思路、多解法代码实现及深度解析，覆盖暴力解法、双端队列（单调队列）最优解法，帮助开发者理解问题本质、掌握解题技巧，同时规避常见误区。本题核心考点为滑动窗口的高效维护、单调队列的应用，是面试高频题，适配中等难度算法练习，重点突破“大数据量下的时间复杂度优化”。

一、题目核心解读

1.1 题目描述（精简版）

给定一个整数数组 nums 和一个正整数 k，有一个大小为 k 的滑动窗口从数组最左侧移动到最右侧，每次向右移动一位。返回每个滑动窗口内的最大值。

核心约束：

• 数据范围：1 ≤ nums.length ≤ 10⁵，-10⁴ ≤ nums[i] ≤ 10⁴，1 ≤ k ≤ nums.length。

• 关键要求：滑动窗口移动过程中，高效获取当前窗口最大值，避免超时（重点突破 10⁵ 量级数据的时间瓶颈）。

1.2 示例解析（直观理解）

示例 1：输入 nums = [1,3,-1,-3,5,3,6,7], k = 3

滑动窗口移动过程及最大值：

• 窗口1：[1,3,-1] → 最大值 3

• 窗口2：[3,-1,-3] → 最大值 3

• 窗口3：[-1,-3,5] → 最大值 5

• 窗口4：[-3,5,3] → 最大值 5

• 窗口5：[5,3,6] → 最大值 6

• 窗口6：[3,6,7] → 最大值 7

输出：[3,3,5,5,6,7]（与示例一致）

示例 2：输入 nums = [1], k = 1 → 窗口唯一，输出 [1]（边界场景，需单独适配）。

关键观察：滑动窗口的核心是“动态维护”——窗口向右移动时，移除左侧离开窗口的元素，加入右侧进入窗口的元素，需快速找到当前窗口的最大值。若每次窗口移动都遍历窗口内元素找最大值，会导致时间复杂度过高，无法适配 10⁵ 量级数据。

二、解题思路深度剖析（3种解法，从暴力到最优）

本题的核心矛盾是“时间复杂度”：暴力解法易实现但超时，最优解法（双端队列）可将时间复杂度降至 O(n)，适配大数据量。以下逐一解析每种解法的思路、优缺点及适用场景。

2.1 解法1：暴力解法（基础思路，适合理解问题）

2.1.1 思路核心

遍历所有可能的滑动窗口，每个窗口内遍历 k 个元素，找到最大值并加入结果集。

具体步骤：

2.1.2 优缺点

• 优点：思路简单、代码易实现，适合新手理解滑动窗口的基本概念。

• 缺点：时间复杂度 O(nk)，当 n=10⁵、k=5×10⁴ 时，运算量达 5×10⁹，远超时间限制，会超时。

2.2 解法2：优先队列（大根堆）解法（优化思路，仍有瓶颈）

2.2.1 思路核心

利用大根堆（堆顶元素为当前堆的最大值），维护滑动窗口内的元素，每次窗口移动时，通过堆快速获取最大值。

具体步骤：

2.2.2 优缺点

• 优点：时间复杂度优化至 O(nlogk)，堆的插入、弹出操作均为 O(logk)，n 个元素共 O(nlogk) 运算，比暴力解法高效。

• 缺点：堆中会存储大量已离开窗口的元素，需要频繁弹出无效元素，在最坏情况下（如数组单调递增），每个元素都需要弹出，仍有一定的性能开销，不是最优解法。

2.3 解法3：双端队列（单调队列）解法（最优解法，面试重点）

2.3.1 思路核心

维护一个双端队列（deque），队列内存储的是 窗口内元素的索引，且索引对应的元素值 单调递减（队列头部为当前窗口的最大值索引）。通过队列的入队、出队操作，动态维护窗口内的有效元素，确保每次窗口移动后，队列头部即为当前窗口的最大值。

核心原则（队列维护规则）：

2.3.2 思路验证（结合示例1）

nums = [1,3,-1,-3,5,3,6,7], k = 3，队列维护过程如下（队列内存储索引，对应元素值标注在括号内）：

• i=0（nums[0]=1）：队列空，加入0 → 队列：[0(1)]

• i=1（nums[1]=3）：3 > 1，移除0，加入1 → 队列：[1(3)]

• i=2（nums[2]=-1）：-1 < 3，直接加入2 → 队列：[1(3), 2(-1)]；此时窗口形成（i=2 ≥ k-1=2），最大值为 nums[1]=3，加入结果。

• i=3（nums[3]=-3）：-3 < -1，加入3 → 队列：[1(3), 2(-1), 3(-3)]；窗口左边界为 3-3+1=1，队列头部1 ≥ 1，最大值为3，加入结果。

• i=4（nums[4]=5）：5 > -3、-1、3，依次移除3、2、1，加入4 → 队列：[4(5)]；窗口左边界为4-3+1=2，头部4 ≥ 2，最大值为5，加入结果。

• i=5（nums[5]=3）：3 < 5，加入5 → 队列：[4(5),5(3)]；窗口左边界为5-3+1=3，头部4 ≥3，最大值为5，加入结果。

• i=6（nums[6]=6）：6 > 3、5，移除5、4，加入6 → 队列：[6(6)]；窗口左边界为6-3+1=4，头部6 ≥4，最大值为6，加入结果。

• i=7（nums[7]=7）：7 > 6，移除6，加入7 → 队列：[7(7)]；窗口左边界为7-3+1=5，头部7 ≥5，最大值为7，加入结果。

最终结果：[3,3,5,5,6,7]，与示例一致，验证思路正确。

2.3.3 优缺点

• 优点：时间复杂度 O(n)，每个元素最多入队、出队各一次，无多余操作；空间复杂度 O(k)，队列内元素个数不超过 k 个，是本题最优解法，适合面试作答。

• 缺点：思路相对复杂，需要理解“单调队列”的维护逻辑，容易出错（如入队时忘记移除小于当前元素的元素、出队时忘记判断边界）。

2.4 常见误区提醒

• 误区1：暴力解法未考虑时间复杂度，直接提交导致超时。需明确 10⁵ 量级数据不能用 O(nk) 解法。

• 误区2：优先队列解法中，只存储元素值，不存储索引，导致无法判断元素是否在当前窗口内，出现错误结果。

• 误区3：单调队列解法中，入队时未移除队列尾部小于当前元素的元素，导致队列不是单调递减，无法快速获取最大值。

• 误区4：单调队列解法中，窗口移动时未判断队列头部是否超出左边界，导致使用了已离开窗口的元素作为最大值。

三、代码实现（Python，3种解法，重点最优解法）

严格按照题目要求的类和方法名格式编写（注：题目要求方法名为 findKthBit，此处按题目实际需求调整为 maxSlidingWindow，贴合题目场景，避免混淆），代码简洁高效，附带详细注释。

3.1 解法1：暴力解法（仅供理解，不推荐提交）

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) –> List[int]:
n = len(nums)
# 滑动窗口的数量为 n – k + 1
res = []
# 遍历所有滑动窗口
for i in range(n – k + 1):
# 当前窗口的范围是 [i, i+k-1]
window = nums[i:i+k]
# 找到窗口内最大值，加入结果
res.append(max(window))
return res

3.2 解法2：优先队列（大根堆）解法（可提交，适合理解堆的应用）

import heapq

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) –> List[int]:
n = len(nums)
res = []
# 初始化大根堆（Python 堆默认是小根堆，存储负数实现大根堆）
heap = []
for i in range(k):
# 存储 (-元素值, 索引)，负数越小，对应原数越大，堆顶即为最大值
heapq.heappush(heap, (–nums[i], i))
# 第一个窗口的最大值（取堆顶的负数的相反数）
res.append(–heap[0][0])

# 滑动窗口向右移动，从 i=k 开始
for i in range(k, n):
# 加入当前元素
heapq.heappush(heap, (–nums[i], i))
# 判断堆顶元素是否在当前窗口内（左边界为 i – k + 1）
while heap[0][1] < i – k + 1:
# 堆顶元素已离开窗口，弹出
heapq.heappop(heap)
# 当前窗口最大值加入结果
res.append(–heap[0][0])
return res

3.3 解法3：双端队列（单调队列）解法（最优，推荐面试使用）

from collections import deque

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) –> List[int]:
n = len(nums)
res = []
# 初始化双端队列，存储窗口内元素的索引，保持队列单调递减
q = deque()

for i in range(n):
# 1. 入队规则：移除队列尾部所有小于当前元素的索引
while q and nums[i] > nums[q[–1]]:
q.pop()
# 加入当前元素的索引
q.append(i)

# 2. 出队规则：判断队列头部是否超出当前窗口左边界（i – k + 1）
while q[0] < i – k + 1:
q.popleft()

# 3. 从 i=k-1 开始，每个窗口都有一个最大值（队列头部）
if i >= k – 1:
res.append(nums[q[0]])
return res

四、代码逐行解析（重点讲解最优解法）

4.1 初始化操作

n = len(nums)
res = []
q = deque()

解释：

• n 存储数组长度，方便后续遍历。

• res 用于存储每个滑动窗口的最大值，最终返回。

• q 是双端队列（deque），核心作用是维护窗口内单调递减的元素索引，队列头部始终是当前窗口的最大值索引。

4.2 遍历数组，维护单调队列

for i in range(n):
# 1. 入队规则：移除队列尾部所有小于当前元素的索引
while q and nums[i] > nums[q[–1]]:
q.pop()
# 加入当前元素的索引
q.append(i)

解释：

• 遍历数组的每个元素，索引为 i，当前元素为 nums[i]。

• while 循环：队列不为空，且当前元素 nums[i] 大于队列尾部索引对应的元素（nums[q[-1]]），则弹出队列尾部索引。原因：这些尾部元素在当前窗口内，比 nums[i] 小，后续窗口移动时，不可能成为最大值，保留无意义，反而会影响最大值的获取。

• 将当前索引 i 加入队列尾部，此时队列仍保持单调递减（从头部到尾部，索引对应的元素值逐渐减小）。

4.3 移除窗口外的无效元素

while q[0] < i – k + 1:
q.popleft()

解释：

• 当前窗口的左边界为 i – k + 1（例如 i=2，k=3，左边界为 0；i=3，k=3，左边界为1）。

• 队列头部的索引 q[0] 若小于左边界，说明该索引对应的元素已离开当前窗口，无法作为当前窗口的最大值，需弹出队列头部，直到队列头部索引在窗口内。

• 此步骤确保队列头部始终是当前窗口内的元素索引。

4.4 收集当前窗口的最大值

if i >= k – 1:
res.append(nums[q[0]])

解释：

• 当 i >= k-1 时，滑动窗口才完全形成（例如 k=3，i=2 时，窗口 [0,1,2] 完全形成），此时队列头部的索引对应的元素，就是当前窗口的最大值。

• 将最大值 nums[q[0]] 加入结果列表 res，完成当前窗口的最大值收集。

五、性能分析与扩展

5.1 三种解法性能对比

5.2 边界场景适配

本题需重点适配3种边界场景，确保代码健壮性：

• 场景1：k=1 → 每个窗口只有一个元素，输出数组本身（代码已适配，i >= 0 时就收集结果）。

• 场景2：n=k → 只有一个窗口，输出 [max(nums)]（代码中 i 从 0 到 n-1，i >= k-1 即 i=n-1 时，收集一次结果）。

• 场景3：数组单调递增/递减 → 单调队列解法仍能高效工作，队列内始终只有1个元素（递增时）或 k 个元素（递减时），时间复杂度仍为 O(n)。

5.3 扩展思考（面试延伸）

答：将单调队列改为“单调递增”即可——入队时，移除队列尾部所有大于当前元素的索引，队列头部即为当前窗口的最小值。

答：核心仍用单调队列，只需动态维护窗口的左边界和右边界，入队、出队规则不变，根据当前窗口大小判断是否收集结果。

答：双端队列解法的空间复杂度已为 O(k)，无法进一步优化（需存储窗口内的有效元素索引），这是最优空间复杂度。

六、总结与思考

6.1 核心知识点

• 滑动窗口的动态维护：窗口移动时，高效移除无效元素、加入新元素，避免重复计算。

• 单调队列的应用：通过维护单调队列，将“找最大值”的时间复杂度从 O(k) 降至 O(1)，是本题的核心技巧。

• 时间复杂度优化：从暴力解法的 O(nk) 到最优解法的 O(n)，体现“空间换时间”的算法思想（用队列存储有效元素，减少重复遍历）。

6.2 解题启示

本题是“滑动窗口 + 单调队列”的经典结合，面试中高频出现。解题时需注意：

• 先理解问题本质，再考虑优化：先实现暴力解法，明确瓶颈所在（时间复杂度），再思考如何通过数据结构（堆、双端队列）优化。

• 单调队列的维护逻辑是关键：牢记“入队去小、出队去超界”，确保队列始终单调递减，头部为最大值索引。

• 边界场景不可忽视：尤其是 k=1、n=k 等特殊情况，需验证代码是否适配。

6.3 测试用例验证

补充4组测试用例，确保代码覆盖所有场景：

• 测试用例1：nums = [1], k = 1 → 输出 [1]（边界场景）。

• 测试用例2：nums = [1,2,3,4,5], k = 2 → 输出 [2,3,4,5]（单调递增）。

• 测试用例3：nums = [5,4,3,2,1], k = 2 → 输出 [5,4,3,2]（单调递减）。

• 测试用例4：nums = [1,-1], k = 1 → 输出 [1,-1]（k=1场景）。

将上述用例代入最优解法代码，均能得到正确结果，验证代码的正确性和健壮性。