数据结构与算法 / 系统课时
单调队列与窗口最值
单调队列与窗口最值
本课解决长度为 k 的滑动窗口最大值问题。单调队列只保留仍可能成为最大值的下标,并同时处理“候选变弱”和“元素过期”两类淘汰,使整体复杂度从 降为 。
学习目标
- 理解单调队列保留最值候选下标的原则
- 掌握队尾淘汰和队头过期的处理顺序
- 实现并验证 的滑动窗口最大值
候选队列如何维护
求窗口最大值时,队列中的下标对应值从队头到队尾单调递减。新元素进入时,从队尾删除所有小于或等于它的旧候选,因为新元素更大且出现更晚;只要它仍在窗口中,这些旧值就不可能再次成为最大值。
窗口左边界右移后,若队头下标小于左边界,说明该元素已离开窗口,应从队头删除。完成两类淘汰后,队头下标对应的值就是当前窗口最大值。

主示例
处理每个右边界 right 时,先维护队尾单调性,再加入当前下标,然后清理队头过期项;当 right >= k - 1 时窗口才完整,可以输出答案。
python
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
if k <= 0 or k > len(nums):
raise ValueError("k 必须位于 1 到数组长度之间")
candidates: deque[int] = deque()
result: list[int] = []
for right, value in enumerate(nums):
# 新值更大且更晚,旧的弱候选可永久淘汰。
while candidates and nums[candidates[-1]] <= value:
candidates.pop()
candidates.append(right)
left = right - k + 1
if candidates[0] < left:
candidates.popleft()
if right >= k - 1:
result.append(nums[candidates[0]])
return result
def main() -> None:
values = [1, 3, -1, -3, 5, 3, 6, 7]
print("窗口最大值:", max_sliding_window(values, 3))
if __name__ == "__main__":
main()预期输出:
text
窗口最大值: [3, 3, 5, 5, 6, 7]复杂度与边界
每个下标只入队一次,并且最多从队头或队尾移除一次,因此总时间复杂度为 。队列最多保存 k 个下标,空间复杂度为 。
队列必须保存下标,否则无法判断元素是否过期。求最小值时反转比较方向,维护单调递增队列。过期条件是 index < left;下标等于左边界时仍属于当前窗口。
易混淆点
普通队列只保证先进先出,不能直接给出窗口最值;单调栈通常解决某个位置左侧或右侧第一个更大、更小元素;单调队列同时受“窗口范围”和“候选强弱”约束,队头始终代表当前窗口答案。
按自己的节奏,确认真正理解。