单调队列优化 DP
当可分离转移的决策窗口左右端点都单调时,用单调队列维护窗口内 y(j,f(j)) 的最小值,把每层转移降为均摊 O(1)。时间 O(n),空间 O(n) · 标签 动态规划 / 单调队列 / 滑动窗口 / DP 优化
问题形式
考虑 1D/1D 动态规划中,当 时,方程退化为
其中
并且 ,窗口左右端点单调。
窗口的左右端点都只会向右移动:新的候选从右侧加入,旧的候选从左侧过期。此时可以用一个单调队列维护窗口内 的最小值。
单调队列
队列中只存下标 ,并按 递增排列。同时要求对应的 也递增;这样队首就是当前窗口的最小值。
计算 时:
- 把所有满足 且尚未加入的 依次加入队尾。
- 若新加入的 对应的值不大于队尾的值,就不断弹出队尾。新下标更大,过期更晚,值又不更差,被弹出的下标不可能再成为最优。
- 弹出所有 的队首元素。
- 取队首作为最优决策,计算 。
每个下标最多入队、出队一次,因此所有转移的总时间是 。
正确性
不变式为:队列中恰好保存当前窗口 内所有未被支配的候选,且它们的值随下标递增。
左端点单调增加,所以被弹出的旧下标以后不会再进入窗口。右端点加入新下标时,若队尾的值不小于新值,队尾下标比新下标更早过期且值更差,未来不可能优于新下标,可以删除。剩下的队首就是窗口最小值。
初始窗口为空,按上述规则加入和删除后, 取到的正是区间最小值。
易错点
- 必须同时要求 和 单调;只要求 单调不足以支持从队首删除。
- 队列中存下标而不是只存值,否则无法判断是否已经小于 。
- 新候选要按 递增加入;不能把尚未算出的 提前放入队列。
- 取最小值时,队尾值等于新值时也可以弹出队尾,保留下标更大的候选;取最大值时方向相反。
- 若窗口为空,队首不存在,需要单独处理无解或基础状态。