11.9 集训记录 & 单调队列入门学习笔记

Zskioaert1106 · 2024-11-09 14:16:36 · 算法·理论

• 本文为单调队列的最基础入门。

单调队列

介绍

单调队列是一种快速查找滑动窗口内最值的方法，其时间复杂度竟可以达到 \mathcal O(n)。

其方法是维护一个队列 q，该队列中存储的是原数列的下标，并总有 q_{i} < q_{i+1} 且 a_{q_i} > a_{q_{i+1}}（此处以求最大值为例）。

每次将滑动窗口最右端的元素 a_i 入队，循环与队尾比较，如果 a_i \geqslant a_{q_{tail}}（tail 为队尾）且队列不为空，则将队尾向前移动并将 i 作为新的 q_{tail}。

然后如果队头的下标不在滑动窗口的范围内就将其AFO删除。最后每次的队头即滑动窗口内的最值。

证明

下面是正确性的证明：

• 对队头的处理使得队列 q 中的所有下标都处于滑动窗口的范围内，不会出现不合法的越界元素。

• 队尾处清除的元素都是在现在及未来的滑动窗口中不再会成为选择的，因为滑动窗口是右移的，所以新的 a_i 一定比队列里原先所有的元素离开的晚，同时它又大于或等于清除的元素，即有 a_i 在，清除的元素就不会派上用场。

• 留下的元素都是还有可能成为选择的，并且越靠前的元素越大，所以队头一定是当前的最优结果。

由于每个元素只会入队、出队一次，所以时间复杂度是 \mathcal O(n)。

代码

通常来讲，单调队列需要存下来数列 a，并使用双端队列（deque）或数组来模拟队列 q。每当读入一个 a_i，就先执行替换队尾并入队，再清除不合法的队头，然后将结果记录下来或输出。

下面是一个求长度为 n 的序列中宽度为 k 的滑动窗口内最大值的单调队列代码：

#include<iostream>
int n,k,a[MAXN],q[MAXN],front=1,tail;
int main(){
    std::cin>>n>>k;
    for(int i=1;i<=n;i++){
        std::cin>>a[i];
        while(front<=tail/*队列不为空*/ && a[q[tail]]<=a[i]/*队尾不比新元素更优*/)
            tail--;
        q[++tail]=i;//将最新元素入队 
        if(i-q[front]>=k)//清除非法队头 
            front++;
        if(i>=k)//输出 
            std::cout<<"左端为"<<i-k+1<<"、右端为"<<i<<"的滑动窗口中最大值为"<<a[q[front]]<<"；\n";
    }
    return 0;
}

注意到清除队头处用的不是 while 而是 if，这是因为该滑动窗口每次右移 1，所以最多会有一个队头变得不合法。

不仅最大，单调队列适用于求各种最值，其本质是一样的。你可以做这几道题以练习单调队列的写法：

• P1886 滑动窗口 /【模板】单调队列
• P2032 扫描
• P1440 求m区间内的最小值

注意单调队列的题目并不都是这么板，比如不连续下标还需要排序的滑动窗口：

• P3088 [USACO13NOV] Crowded Cows S

用途

单调队列通常不是直接作为考点出现在题目中，而是用以优化动态规划或其它算法。

• P1714 切蛋糕

这道题可以用前缀和做，即求最大的 a_i-a_j(1\le j< i)，其中 a 为前缀和数组。每个 a_i 是固定的，那么就可以转化为求最小的 a_j。每次让答案 ans=\max(ans,a_{q_{front}})，然后把 a_i 加进单调队列里，最后的结果就是用 O(n) 模拟出来的。

• P1725 琪露诺

这道题是明鲜的动态规划，先把转移方程列出来：f_i=\max\limits_{j=i-R}^{i-L}f_j+a_i，直接枚举会超时，那么显然可以用单调队列优化。每次让 f_i 入队，然后使 f_{i+L}=a_{i+L}+f_{q_{front}}，结果是所有下一步可以到达对岸的位置中权值最大的一个即 \max\limits_{i=N-R+L}^{N}f_i。

当然这样你就会被 hack，所以要注意 L=R 的情况。

• P1419 寻找段落

思考：这道题很像上面两道题的结合版，应该怎么把两道的思路结合起来？