数据结构与算法 / 系统课时
用单调队列维护窗口最值
用单调队列维护窗口最值
滑动窗口每移动一次,都要删除离开窗口的元素并加入一个新元素。如果每次重新扫描整个窗口,时间复杂度会退化到 。单调队列通过同时淘汰失效索引和不可能成为最值的元素,把窗口最大值或最小值在线维护到线性复杂度。
学习目标
- 理解单调队列中为什么保存索引而不是只保存元素值
- 掌握删除失效索引、淘汰无竞争力元素和读取窗口最值的固定顺序
- 能写出 的滑动窗口最大值算法,并判断其边界条件
队列里只保留仍有竞争力的元素
以窗口最大值为例,双端队列 deque 保存数组索引,并让对应元素值从队首到队尾严格递减。这样,队首始终是当前窗口最大值的索引。
当新元素 nums[i] 到来时,如果队尾元素小于等于它,那么这些旧元素已经失去竞争力:新元素更大或相等,而且索引更新,会比旧元素更晚离开窗口。因此可以从队尾连续删除它们。
另一方面,窗口左边界不断右移,所以队首索引一旦满足 deque[0] <= i - k,就已经不属于当前窗口,必须先移除。队列因此同时表达两个约束:索引必须仍在窗口内,值必须保持单调。

维护顺序
处理位置 i 时,可以固定按下面的顺序思考:
- 删除队首已经离开窗口的索引。
- 从队尾删除值小于等于
nums[i]的索引。 - 把索引
i加入队尾。 - 当第一个完整窗口形成后,读取队首对应值作为当前最大值。
这里保存索引非常关键。只保存元素值虽然能比较大小,却无法可靠判断某个元素何时已经滑出窗口。
主示例
下面实现 LeetCode 239「滑动窗口最大值」的核心算法。为了让相等元素也保持最简队列,遇到新值时使用 <= 删除旧的相等元素,让更晚过期的新索引留下。
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
if not nums or k <= 0 or k > len(nums):
return []
dq: deque[int] = deque()
result: list[int] = []
for i, value in enumerate(nums):
# 队首索引若已经落到窗口左边界之外,就先淘汰。
while dq and dq[0] <= i - k:
dq.popleft()
# 队尾比新元素更小或相等时,未来不可能再成为最大值。
while dq and nums[dq[-1]] <= value:
dq.pop()
dq.append(i)
# i >= k - 1 时,第一个完整窗口已经形成。
if i >= k - 1:
result.append(nums[dq[0]])
return result
if __name__ == "__main__":
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(max_sliding_window(nums, 3))预期输出:
[3, 3, 5, 5, 6, 7]为什么能做到线性复杂度
虽然代码里有两个 while,但同一个索引只会从队尾进入一次,也最多从队首或队尾离开一次。整个数组遍历期间,所有入队和出队操作总数都是 ,因此时间复杂度为 ,队列最多保存一个窗口中的索引,空间复杂度为 。
单调队列并不是保存窗口全部数据,而是在维护一个“仍可能成为答案的候选集合”。这也是它比堆更适合固定方向滑动窗口的原因:过期元素可以直接从队首判断,而最大值读取始终是 。
最小值与边界
如果要求窗口最小值,只需要把队列改成对应值单调递增:新元素到来时,从队尾删除所有大于等于它的元素,其他逻辑完全相同。
k = 1 时,每个元素自己就是一个窗口;k = len(nums) 时只产生一个结果。若题目没有保证 1 <= k <= len(nums),实现中还应像主示例一样先处理非法窗口大小。真正需要记住的不是某段模板,而是两类淘汰条件:队首负责处理过期,队尾负责处理失去竞争力的候选者。