239. 滑动窗口最大值
题目描述
给你一个整数数组 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^41 <= k <= nums.length
解题思路
第一步：理解问题本质
滑动窗口问题需要维护一个固定大小的窗口，并在窗口滑动时快速获取窗口内的最大值。
关键观察：
- 窗口每次只移动一位，只有一个元素离开窗口，一个元素进入窗口
- 如果使用暴力方法，每个窗口都遍历求最大值，时间复杂度是 O(n*k)
- 需要一种数据结构，能够高效维护窗口内的最大值
第二步：暴力解法
对于每个窗口位置，遍历窗口内的 k 个元素求最大值。
def maxSlidingWindow_brute(nums, k):
n = len(nums)
result = []
for i in range(n - k + 1):
window_max = nums[i]
for j in range(i, i + k):
window_max = max(window_max, nums[j])
result.append(window_max)
return result
为什么不够好？
- 时间复杂度 O(n*k)，当 n=10^5, k=10^5 时会超时
- 没有利用窗口滑动的特性，做了很多重复比较
第三步：优化解法 - 使用堆
使用优先队列（大顶堆）维护窗口内的元素。
from heapq import heappush, heappop
def maxSlidingWindow_heap(nums, k):
n = len(nums)
result = []
max_heap = [] # 存储 (-值, 下标)
for i in range(n):
heappush(max_heap, (-nums[i], i))
# 移除窗口外的元素
while max_heap[0][1] <= i - k:
heappop(max_heap)
# 窗口形成后开始记录答案
if i >= k - 1:
result.append(-max_heap[0][0])
return result
复杂度分析：
- 时间复杂度 O(n*log n) - 每个元素入堆出堆各一次
- 空间复杂度 O(n) - 堆的空间
第四步：最优解法 - 单调队列
使用单调递减队列，队列中存储元素下标，对应的值单调递减。
核心思想：
- 队列头部始终是当前窗口的最大值
- 新元素入队时，所有比它小的元素都不可能成为后续窗口的最大值，直接弹出
- 使用下标可以判断队首元素是否已滑出窗口
算法流程（三步骤）：
- 右边入：新元素从队尾入队，维护单调递减性质
- 左边出：检查队首是否滑出窗口，若是则弹出
- 记录答案：当窗口形成后，队首即为当前窗口最大值
完整代码实现
from typing import List
from collections import deque
class Solution:
"""
239. 滑动窗口最大值 - 单调队列解法
核心思路：
使用单调递减队列维护窗口内的最大值候选。队列中存储的是元素下标，
对应的元素值从队首到队尾单调递减。
算法流程（三步骤）：
1. 右边入：新元素从队尾入队，维护单调递减性质
2. 左边出：检查队首是否滑出窗口，若是则弹出
3. 记录答案：当窗口形成后（i >= k-1），队首即为当前窗口最大值
时间复杂度: O(n) - 每个元素最多入队出队各一次
空间复杂度: O(k) - 队列中最多存储 k 个元素
"""
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
ans = [0] * (n - k + 1) # 窗口个数为 n - k + 1
q = deque() # 双端队列，存储下标，对应元素值单调递减
for i, x in enumerate(nums):
# 步骤1：右边入 - 维护单调递减性质
# 新元素 x 入队前，弹出所有比 x 小的元素
# 这些被弹出的元素不可能成为后续窗口的最大值
while q and nums[q[-1]] <= x:
q.pop()
q.append(i) # 保存下标以便判断元素是否滑出窗口
# 步骤2：左边出 - 检查队首是否滑出窗口
left = i - k + 1 # 当前窗口的左端点
if q[0] < left: # 队首元素已不在窗口内
q.popleft()
# 步骤3：记录答案
# 当窗口完全形成后（left >= 0），队首即为当前窗口最大值
if left >= 0:
ans[left] = nums[q[0]]
return ans
示例推演
以 nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 为例：
| i | nums[i] | 入队前队列 | 入队操作 | 出队后队列 | left | 是否记录 | ans |
|---|---|---|---|---|---|---|---|
| 0 | 1 | [] | 加入 0 | [0] | -2 | 否 | - |
| 1 | 3 | [0] | 弹出 0，加入 1 | [1] | -1 | 否 | - |
| 2 | -1 | [1] | 加入 2 | [1, 2] | 0 | 是，ans[0]=3 | [3] |
| 3 | -3 | [1, 2] | 加入 3 | [1, 2, 3] | 1 | 是，ans[1]=3 | [3, 3] |
| 4 | 5 | [1, 2, 3] | 弹出 1,2,3，加入 4 | [4] | 2 | 是，ans[2]=5 | [3, 3, 5] |
| 5 | 3 | [4] | 加入 5 | [4, 5] | 3 | 是，ans[3]=5 | [3, 3, 5, 5] |
| 6 | 6 | [4, 5] | 弹出 4,5，加入 6 | [6] | 4 | 是，ans[4]=6 | [3, 3, 5, 5, 6] |
| 7 | 7 | [6] | 弹出 6，加入 7 | [7] | 5 | 是，ans[5]=7 | [3, 3, 5, 5, 6, 7] |
关键观察：
- 当 5 进入时，队列中的 1, -1, -3 都比 5 小，全部弹出，因为 5 在窗口期间它们不可能成为最大值
- 队列始终保持单调递减，队首就是当前窗口最大值
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力 | O(n*k) | O(1) | 每个窗口遍历求最大值，超时 |
| 堆 | O(n*log n) | O(n) | 使用优先队列，每次操作 log n |
| 单调队列 | O(n) | O(k) | 每个元素最多入队出队各一次，最优 |
易错点总结
1. 队列中存储的是下标而非值
错误做法： 直接存储数值，无法判断元素是否滑出窗口。
正确做法： 存储下标，通过比较下标和窗口左端点判断是否滑出。
# 正确：存储下标
q.append(i)
if q[0] < left: # 通过下标判断是否滑出
q.popleft()
2. 使用 <= 而非 < 维护单调性
错误做法： nums[q[-1]] < x，会导致相等的元素留在队列中。
正确做法： nums[q[-1]] <= x，相等时也弹出，保证严格递减。
3. 记录答案的时机
错误做法： 在每次循环都记录答案。
正确做法： 只有当 left >= 0（即窗口完全形成）后才记录。
if left >= 0: # 窗口已形成
ans[left] = nums[q[0]]
4. 边界处理
- 数组长度为 1，k = 1
- 所有元素相等
- 数组严格递增或递减
扩展思考
1. 相关题目
- 239. 滑动窗口最大值 - 单调队列经典题
- 1438. 绝对差不超过限制的最长连续子数组 - 双单调队列
- 862. 和至少为 K 的最短子数组 - 单调队列优化 DP
2. 单调队列的本质
单调队列是一种"维护候选集合"的数据结构：
- 当新元素加入时，所有"不可能成为答案"的旧元素被移除
- 队列头部始终是当前最优解
- 适用于滑动窗口最值问题
3. 变体问题
如果需要滑动窗口最小值，只需将单调递减改为单调递增即可。