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

用单调队列优化滑动转移

用单调队列优化滑动转移

当动态规划的某个状态只需要查询前面固定窗口中的最大值或最小值时,逐个扫描窗口会把大量比较重复执行。本篇把这种转移改造成单调队列维护候选,使一次窗口查询从线性扫描降为均摊常数时间。

学习目标

  • 识别可以使用单调队列优化的滑动窗口型状态转移
  • 正确处理候选入队、劣质候选淘汰和窗口过期
  • 将 O(nk) 的直接转移优化为 O(n) 时间复杂度

从重复扫描中找到优化点

考虑状态转移:当前位置 i 可以从前面至多 k 个位置跳来,并获得当前位置的分数。若 dp[i] 表示到达 i 的最大总分,则有 dp[i] = score[i] + max(dp[j]),其中 i-k <= j < i。

直接实现会对每个 i 扫描最多 k 个前驱。当状态数为 n 时,时间复杂度达到 O(nk)。真正昂贵的部分不是动态规划本身,而是不断对高度重叠的窗口重新求最大值。

例如从 i 移到 i+1 时,旧窗口通常只删除最左侧一个位置并加入一个新位置。若能保留仍可能成为最大值的候选,就不必重新扫描整个窗口。

单调队列只保存有竞争力的候选

维护一个双端队列,其中存放状态下标,并保证对应的 dp 值从队首到队尾单调递减。这样,队首始终是当前有效窗口里的最大状态,可以直接用于下一次转移。

处理位置 i 时依次执行三个动作:先删除已经落到 i-k 左侧的过期下标;再使用队首计算 dp[i];最后从队尾删除所有 dp 不大于 dp[i] 的候选,并把 i 加入队尾。

队尾候选之所以可以删除,是因为新状态 i 更晚过期,而且值又不小于它们。只要 i 仍在窗口中,这些旧候选就不可能比 i 更适合作为最大值来源。

滑动转移中的单调队列维护过程

实现最大值滑动转移

下面的程序计算一条只能向前跳最多 k 步的路径最大得分。队列保存的是下标而不是分数,因为判断元素是否过期需要知道它的位置。

python
from collections import deque


def max_window_dp(score, k):
    if not score:
        raise ValueError('score must not be empty')
    if k <= 0:
        raise ValueError('k must be positive')

    n = len(score)
    dp = [0] * n
    dp[0] = score[0]
    candidates = deque([0])

    for i in range(1, n):
        # 先移除已经不属于 [i-k, i-1] 的状态。
        while candidates and candidates[0] < i - k:
            candidates.popleft()

        dp[i] = score[i] + dp[candidates[0]]

        # 新状态更晚过期,且不小于队尾时可永久替代队尾候选。
        while candidates and dp[candidates[-1]] <= dp[i]:
            candidates.pop()
        candidates.append(i)

    return dp[-1], dp


best, states = max_window_dp([1, -1, -2, 4, -7, 3], 2)
print('best =', best)
print('dp =', states)

预期输出

text
best = 7
dp = [1, 0, -1, 4, -3, 7]

这里每个下标最多入队一次、从队首或队尾移除一次,因此所有队列操作的总次数与 n 同阶。转移时间从 O(nk) 降为 O(n),队列本身最多保存 k 个有效候选。

淘汰顺序决定结果是否正确

过期检查必须发生在读取队首之前,否则已经离开窗口的旧最大值仍可能参与当前转移。另一个常见错误是只保存 dp 值;值本身无法判断对应状态何时越过窗口左边界,因此通常应保存下标。

对于最大值转移,队列维护递减序列;若转移依赖窗口最小值,则把比较方向反过来维护递增序列。使用 <= 淘汰相等的旧候选通常更省空间,因为相同数值下,更晚进入的状态拥有更长的有效期。

单调队列适用于窗口边界随状态单向移动、查询目标是窗口极值的模型。如果转移需要窗口内元素之和、任意排序统计量,或候选集合并非连续滑动窗口,就应重新判断数据结构,而不是机械套用单调队列。

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

目录与阅读设置

阅读设置

17

记录一个想法

用单调队列优化滑动转移

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

登录哪都通