浅谈单调队列

ycw123 · 2021-07-31 12:00:43 · 个人记录

单调队列，顾名思义就是一个元素之间的关系具有单调性的队列

我们通过一道例题来讲解

最大子序和

题目大意

给定一个长度为 N 的整数序列（可能有负数），从中找出一段长度不超过 M 的连续子序列，使得子序列中所有数的和最大。 N,M \le 3 \cdot 10^5 。

solution

计算“区间和”的问题，一般转化为“两个前缀和相减”的形式进行求解。我们先求出 S[i] 表示序列里前 i 项的和，则连续子序列 [L，R] 中的数的和就等于 S[R] - S[L-1]。那么原问题就可以转化为：

找出两个位置 x,y 使 S[y] - S[x] 最大并且 y - x \le M。

首先我们枚举右端点 i，当 i 固定时，问题就变为：

找到一个左端点 j，其中 j \in [i-m,i-1] 并且 S[j] 最小。

不妨比较一下任意两个位置 j 和 k，

如果 k<j<i 并且 S[k] \ge S[j]，

那么对于所有大于等于 i 的右端点，k 永远不会成最优选择。

这是因为不但 S[k] \not < S[j]，而且 j 离 i 更近，长度更不容易超过 M，即 j 的生存能力比 k 更强。所以当 j 出现后，k 就完全是一个无用的位置。

以上比较告诉我们，可能成为最优选择的策集合一定是一个

“下标位置递增、对应的前缀和S的值也递增” 的序列。

我们可以用一个队列保存这个序列。随着右端点位置改变,从前向后扫描，我们对每个 i 执行以下三个步骤：

1. 判断队头决策与 i 的距离是否超出 M 的范围，若超出则出队。
2. 此时队头就是右端点为 i 时，左端点 j 的最优选择。
3. 不断删除队尾决策，直到队尾对应的S值小于 S[i]。然后把 i 作为一个新的决策入队。

实现方法：STL双端队列 或 手写（此处只展示了双端队列代码）

deque<int> q;
while(q.size()) q.pop_front();
q.push_back(0);
for(int i=1;i<=n;i++){
    while(q.size()&&i-q.front()>k) q.pop_front();
    ans=max(ans,sum[i]-sum[q.front()]);
    while(q.size()&&sum[q.front()]>=sum[i]) q.pop_back();
    q.push_back(i);
}

这就是著名的单调队列算法，因为每个元素至多入队一次、出队一次,所以整个算法的时间复杂度为 O(N)。

它的思想也是 在决策集合(队列)中及时排除一定不是最优解的选择。 单调队列也是优化动态规划的一个重要手段。

练习题

滑动窗口 /【模板】单调队列