数据结构与算法 / 系统课时

单调队列与窗口最值

单调队列与窗口最值

本课解决长度为 k 的滑动窗口最大值问题。单调队列只保留仍可能成为最大值的下标,并同时处理“候选变弱”和“元素过期”两类淘汰,使整体复杂度从 O(nk)O(nk) 降为 O(n)O(n)。

学习目标

  • 理解单调队列保留最值候选下标的原则
  • 掌握队尾淘汰和队头过期的处理顺序
  • 实现并验证 O(n)O(n) 的滑动窗口最大值

候选队列如何维护

求窗口最大值时,队列中的下标对应值从队头到队尾单调递减。新元素进入时,从队尾删除所有小于或等于它的旧候选,因为新元素更大且出现更晚;只要它仍在窗口中,这些旧值就不可能再次成为最大值。

窗口左边界右移后,若队头下标小于左边界,说明该元素已离开窗口,应从队头删除。完成两类淘汰后,队头下标对应的值就是当前窗口最大值。

单调队列维护滑动窗口最大值

主示例

处理每个右边界 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]

复杂度与边界

每个下标只入队一次,并且最多从队头或队尾移除一次,因此总时间复杂度为 O(n)O(n)。队列最多保存 k 个下标,空间复杂度为 O(k)O(k)。

队列必须保存下标,否则无法判断元素是否过期。求最小值时反转比较方向,维护单调递增队列。过期条件是 index < left;下标等于左边界时仍属于当前窗口。

易混淆点

普通队列只保证先进先出,不能直接给出窗口最值;单调栈通常解决某个位置左侧或右侧第一个更大、更小元素;单调队列同时受“窗口范围”和“候选强弱”约束,队头始终代表当前窗口答案。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

单调队列与窗口最值

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通