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

用单调队列维护窗口最值

用单调队列维护窗口最值

滑动窗口每移动一次,都要删除离开窗口的元素并加入一个新元素。如果每次重新扫描整个窗口,时间复杂度会退化到 O(nk)O(nk)。单调队列通过同时淘汰失效索引和不可能成为最值的元素,把窗口最大值或最小值在线维护到线性复杂度。

学习目标

  • 理解单调队列中为什么保存索引而不是只保存元素值
  • 掌握删除失效索引、淘汰无竞争力元素和读取窗口最值的固定顺序
  • 能写出 O(n)O(n) 的滑动窗口最大值算法,并判断其边界条件

队列里只保留仍有竞争力的元素

以窗口最大值为例,双端队列 deque 保存数组索引,并让对应元素值从队首到队尾严格递减。这样,队首始终是当前窗口最大值的索引。

当新元素 nums[i] 到来时,如果队尾元素小于等于它,那么这些旧元素已经失去竞争力:新元素更大或相等,而且索引更新,会比旧元素更晚离开窗口。因此可以从队尾连续删除它们。

另一方面,窗口左边界不断右移,所以队首索引一旦满足 deque[0] <= i - k,就已经不属于当前窗口,必须先移除。队列因此同时表达两个约束:索引必须仍在窗口内,值必须保持单调。

滑动窗口最大值中的单调队列维护过程

维护顺序

处理位置 i 时,可以固定按下面的顺序思考:

  1. 删除队首已经离开窗口的索引。
  2. 从队尾删除值小于等于 nums[i] 的索引。
  3. 把索引 i 加入队尾。
  4. 当第一个完整窗口形成后,读取队首对应值作为当前最大值。

这里保存索引非常关键。只保存元素值虽然能比较大小,却无法可靠判断某个元素何时已经滑出窗口。

主示例

下面实现 LeetCode 239「滑动窗口最大值」的核心算法。为了让相等元素也保持最简队列,遇到新值时使用 <= 删除旧的相等元素,让更晚过期的新索引留下。

python
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))

预期输出:

text
[3, 3, 5, 5, 6, 7]

为什么能做到线性复杂度

虽然代码里有两个 while,但同一个索引只会从队尾进入一次,也最多从队首或队尾离开一次。整个数组遍历期间,所有入队和出队操作总数都是 O(n)O(n),因此时间复杂度为 O(n)O(n),队列最多保存一个窗口中的索引,空间复杂度为 O(k)O(k)。

单调队列并不是保存窗口全部数据,而是在维护一个“仍可能成为答案的候选集合”。这也是它比堆更适合固定方向滑动窗口的原因:过期元素可以直接从队首判断,而最大值读取始终是 O(1)O(1)。

最小值与边界

如果要求窗口最小值,只需要把队列改成对应值单调递增:新元素到来时,从队尾删除所有大于等于它的元素,其他逻辑完全相同。

k = 1 时,每个元素自己就是一个窗口;k = len(nums) 时只产生一个结果。若题目没有保证 1 <= k <= len(nums),实现中还应像主示例一样先处理非法窗口大小。真正需要记住的不是某段模板,而是两类淘汰条件:队首负责处理过期,队尾负责处理失去竞争力的候选者。

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

目录与阅读设置

阅读设置

17

记录一个想法

用单调队列维护窗口最值

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

登录哪都通