跳转至

单调队列

概述ψ(｀∇´)ψ

单调队列，顾名思义，就是队列里的元素以某种方式单调的队列。

有一个很出名的梗，“比你小，比你强”，可以用来理解单调队列。

单调队列可以处理一些滑动的区间内的静态最值问题。

复杂度从暴力的 \(O(nm)\) 变成了 \(O(n)\)。

应用ψ(｀∇´)ψ

有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值。

考虑维护一个队列，存储当前区间的所有元素。

然后我们考虑保持队列的单调性，让队头永远是最大的，后面以此递减。

每次滑动的时候把过时的那一个扔出去，新的扔进来，然后你发现，如果储存所有元素的话，大概率要弹出的时候没法从队列里拿出来。

而且如果这样做要保持单调性，每次都还要排序，复杂度就变成了 \(O(n^2\log n)\)，不如暴力！

然后你发现其实没有必要存储所有元素，如果一个元素本来在队列中间，进来一个新的数之后它的位置往后退了，很明显他就是一个“冗余决策”。

因为有一个比你后进来，剩余有效期比你多的，实力比你强的，不管怎么样，在你有效的期间，你都不可能超过他，我们这里只需要最大值，所以你既然永远不可能成为头了，那我就把你弹掉。

然后队头可以一直保持最大值，且队列里的下标也是单调递增的，这样过期的时候只用把队头弹出就行了！

模拟一下这个过程：

\(\{a\} = 5, 7, 2, 8, 4, 7, 9\)， \(k = 3\)。

初始化队列：把 \(5\) 放进来，然后发现有比他小比他强的 \(7\)，弹掉，队列只剩 \(7\)，\(2\) 虽然比 \(7\) 小，但是 \(7\) 如果过期了之后说不定 \(2\) 可以，所以入队，此时队列为 \(|7, 2|\)

  • 移动一次：发现 \(8\) 能把 \(7,2\) 全部暴杀，所以 \(7, 2\) 弹掉，只剩 \(8\)。

  • 移动两次：\(4\) 也许可以，放进来：\(|8, 4|\)。

  • 移动三次：\(7\) 把 \(4\) 暴杀，\(4\) 弹掉，\(7\) 入队，变成 \(|8, 7|\)。

  • 移动四次：\(8\) 过期，弹掉，剩下 \(7\)，然后 ⑨ 把 \(7\) 暴杀，队列只剩 ⑨。

实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>

using namespace std;

const int si = 1e6 + 10;

int n, k;
int a[si], ans[si];
int q[si], hd = 1, tl = 0; 

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.badbit | cin.failbit);

    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 1; i <= n; ++i) {
        while(hd <= tl && q[hd] + k <= i) 
            hd++;//排除队头过期的。
        while(hd <= tl && a[i] <= a[q[tl]]) 
            tl--;//排除队尾冗杂决策。
        q[++tl] = i;
        ans[i] = a[q[hd]];//注意这里q存的是下标，所以要将其作为下标。
    }
    return 0;
}

Warning

注意这里 \(head\) 和 \(tail\) 的初值是 head = 1, tail = 0。

这种写法对应的是维护闭区间 \([head, tail]\)

如果维护左闭右开区间 \([head,tail)\)，那么初值应当是 head = 1, tail = 1。

这个在斜率优化里面使用到单调队列时也提到过。

不止单调队列，莫队这种算法也是一样，\(l,r\) 的初值和移动方式决定了维护的区间性质。

单调队列还可以用来优化 DP。

总结ψ(｀∇´)ψ

mq-1.png

在每道题使用单调队列之前需要看清题目的端点取舍和条件。

比如求 m 区间内的最小值那道题就是求 \([i-k-1,i)\) 的最小值.

所以说最好在用之前手玩一下数据。

最后更新: May 9, 2023