单调队列学习笔记

本文章最后更新日期为:2021-08-26

单调队列是什么

单调栈类似,单调队列同样本质上仍任是一个队列,不过队列中的元素是有序的。

单调队列用来干什么

众所周知,单调队列主要用来解决滑动窗口问题。

滑动窗口问题所指的是在给定的序列 mm 中寻找所有长度为 kk 连续区域 [l,r]\left[l, r\right] 内的最大值 / 最小值问题。

而使用单调队列解决滑动窗口的时间复杂度为 O(n)O(n),比 ST 表、线段树、树状数组、平衡树更优。

单调队列的思想

洛谷 P1886 滑动窗口 /【模板】单调队列为例子介绍。

创建两个 deque 作为单调队列(一个存储最大值,另一个最小值)。

样例:
当我们读入整个序列之后,开始遍历,初始时 ii 的位置如下:

a:13135367dequemax:emptydequemin:emptya: \colorbox{RoyalBlue}{\color{Red}{1}} \quad 3 \quad -1 \quad -3 \quad 5 \quad 3 \quad 6 \quad 7 \newline deque_{max}: \text{empty} \newline deque_{min}: \text{empty}

由于此时的长度还不满足 kk,并且两个 deque 都为空,所以将 11 的下表 1 加入两个 deque。接着将 i 自增。

为什么是添加下标到队列中而不是值?

为了在长度超过 kk 时对队列进行元素弹出,所以添加下标进入队列中以便判断,并且也可以通过下标访问对应的值,但通过值查找下标就显得十分不便。

a:3135367dequemax:1dequemin:1a: \colorbox{RoyalBlue}{1 \quad \color{Red}{3}} \quad -1 \quad -3 \quad 5 \quad 3 \quad 6 \quad 7 \newline deque_{max}: 1 \newline deque_{min}: 1

当我们将要把 33 加入 dequeMax 时,发现里边已经非空,于是进行以下操作:

  1. 判断新加入的 xxdeque 的最后一位 endend 对应的 aenda_{end} 进行比较,如果 xaendx \geqslant a_{end} 就将 endend 弹出,并且重复此操作直到 x<aendx < a_{end}
  2. 加入 xx 的下标 ideque 中。

最小值同理。

为啥要又弹又加的?

为了确保两个 deque 中元素之中按照一定的顺序进行排列,我们在添加之前需要将不符合顺序的元素弹出(当然因为我们求的是最大值 / 最小值,所以弹出不是最大值 / 最小值的元素对答案并无影响)。

进行完以上操作后结果如下:

a:3135367dequemax:2dequemin:1a: \colorbox{RoyalBlue}{1 \quad \color{Red}{3}} \quad -1 \quad -3 \quad 5 \quad 3 \quad 6 \quad 7 \newline deque_{max}: 2 \newline deque_{min}: 1

继续进行下一次操作,操作完成之后:

a:-135367dequemax:2dequemin:3a: \colorbox{RoyalBlue}{1 \quad 3 \quad \color{Red}{-1}} \quad -3 \quad 5 \quad 3 \quad 6 \quad 7 \newline deque_{max}: 2 \newline deque_{min}: 3

继续!

a:1-1 -35367dequemax:2dequemin:3a: \colorbox{Salmon}{1} \quad \colorbox{RoyalBlue}{3 \quad -1 \quad \color{Red}{-3}} \quad 5 \quad 3 \quad 6 \quad 7 \newline deque_{max}: 2 \newline deque_{min}: 3

此时发现长度大于 kk 了,进行以下操作:

  1. 先判断 xx 加入 deque 中。
  2. 如果 deque 的开头的元素的下标 startstart 小于等于 iki - k,说明该下标所对应的值不再被包含在区间之内,将 startstartdeque 中弹出。

最小值同理。

那么如何维护答案呢?
我们惊讶的发现,当 iki \geqslant k 时,需要输出此时的答案,那么此时的答案也正好为两个 deque 的队列头部。
所以将他们添加到答案序列 ans 中(并不弹出)。

最后是每一步的状态示意:

a:-135367dequemax:2dequemin:3ansmax:a2ansmin:a3a: \colorbox{RoyalBlue}{1 \quad 3 \quad \color{Red}{-1}} \quad -3 \quad 5 \quad 3 \quad 6 \quad 7 \newline deque_{max}: 2 \newline deque_{min}: 3 \newline ans_{max}: a_{2} \newline ans_{min}: a_{3}

a:1-1 -35367dequemax:2dequemin:4ansmax:a2a2ansmin:a3a4a: 1 \quad \colorbox{RoyalBlue}{3 \quad -1 \quad \color{Red}{-3}} \quad 5 \quad 3 \quad 6 \quad 7 \newline deque_{max}: 2 \newline deque_{min}: 4 \newline ans_{max}: a_{2} \quad a_{2} \newline ans_{min}: a_{3} \quad a_{4}

a:13-1 -3 5367dequemax:5dequemin:4ansmax:a2a2a5ansmin:a3a4a4a: 1 \quad 3 \quad \colorbox{RoyalBlue}{-1 \quad -3 \quad \color{Red}{5}} \quad 3 \quad 6 \quad 7 \newline deque_{max}: 5 \newline deque_{min}: 4 \newline ans_{max}: a_{2} \quad a_{2} \quad a_{5} \newline ans_{min}: a_{3} \quad a_{4} \quad a_{4}

a:131-3 367dequemax:5dequemin:4ansmax:a2a2a5a5ansmin:a3a4a4a4a: 1 \quad 3 \quad -1 \quad \colorbox{RoyalBlue}{-3 \quad 5 \quad \color{Red}{3}} \quad 6 \quad 7 \newline deque_{max}: 5 \newline deque_{min}: 4 \newline ans_{max}: a_{2} \quad a_{2} \quad a_{5} \quad a_{5} \newline ans_{min}: a_{3} \quad a_{4} \quad a_{4} \quad a_{4}

a:131367dequemax:7dequemin:6ansmax:a2a2a5a5a7ansmin:a3a4a4a416a: 1 \quad 3 \quad -1 \quad -3 \quad \colorbox{RoyalBlue}{5 \quad 3 \quad \color{Red}{6}} \quad 7 \newline deque_{max}: 7 \newline deque_{min}: 6 \newline ans_{max}: a_{2} \quad a_{2} \quad a_{5} \quad a_{5} \quad a_{7} \newline ans_{min}: a_{3} \quad a_{4} \quad a_{4} \quad a_{4} \quad 1_{6}

a:131357dequemax:8dequemin:6ansmax:a2a2a5a5a7a8ansmin:a3a4a4a416a6a: 1 \quad 3 \quad -1 \quad -3 \quad 5 \quad \colorbox{RoyalBlue}{3 \quad 6 \quad \color{Red}{7}} \newline deque_{max}: 8 \newline deque_{min}: 6 \newline ans_{max}: a_{2} \quad a_{2} \quad a_{5} \quad a_{5} \quad a_{7} \quad a_{8} \newline ans_{min}: a_{3} \quad a_{4} \quad a_{4} \quad a_{4} \quad 1_{6} \quad a_{6}

最后的答案序列也就是:

ansmax:335567ansmin:133333ans_{max}: 3 \quad 3 \quad 5 \quad 5 \quad 6 \quad 7 \newline ans_{min}: -1 \quad -3 \quad -3 \quad -3 \quad 3 \quad 3

code:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <deque>
#include <iostream>
#include <vector>

using namespace std;

class Num {
public:
int32_t id, val;

Num(const int32_t id, const int32_t val) {
this->id = id;
this->val = val;
}
};

int32_t n, k;
deque<Num> deq[2];
vector<int32_t> ans[2];

int main() {
cin >> n >> k;

Num tmp = Num(0, 0);
for (int32_t i = 1, x; i <= n; ++i) {
cin >> x;
tmp = Num(i, x);
while (deq[0].size() && x >= deq[0].back().val) {
deq[0].pop_back();
}
while (deq[1].size() && x <= deq[1].back().val) {
deq[1].pop_back();
}

deq[0].push_back(tmp);
deq[1].push_back(tmp);

while (i - k >= deq[0].front().id) {
deq[0].pop_front();
}
while (i - k >= deq[1].front().id) {
deq[1].pop_front();
}

if (i >= k) {
ans[0].push_back(deq[1].front().val);
ans[1].push_back(deq[0].front().val);
}
}

for (auto i : ans[0]) {
cout << i << ' ';
}
cout << endl;
for (auto i : ans[1]) {
cout << i << ' ';
}
cout << endl;

return 0;
}

时间复杂度的小小说明

什么?你说 for 里套了一个 while 复杂度就是 O(n2)O(n^{2}) 了? 非也非也。
deque 中的数是我们之前所添加进来的,也就是说每一个数只会进入 deque 中一次,所以只要 while 或者不在 kk 的范围内了就会被弹出。
所以即使 whilefor 里,单调队列的时间复杂度依然是 O(n)O(n)

什么?神犇你说太简单了?那么来点更刺激的行不行?

二维滑动窗口

洛谷 P2216 [HAOI2007] 理想的正方形为例,来看看二维的滑动窗口应该如何是好。

我们需要在一个二维的矩阵中计算最大值与最小值,显然可以使用滑动窗口来解决,但是现在还不是说 “就这?” 的时候,我们仍然需要仔细思考这个二维的滑动窗口问题。

如果将一维的滑动窗口模版套上你会发现这是行不通的。

为什么行不通?

当我们直接使用一维的模版时,每一个元素不仅仅进入队列中一次,而是多次进入队列(当需要更换行数,比如从第二行到第三行时),导致性能下降。

经过我们的苦思冥想,终于发现:我们并不需要直接进行二维的滑动窗口,一维一维的做不就行了?

首先在这个 a×ba \times b 的矩阵中,我们需要找出 n×nn \times n 的一个区域(其实 n×mn \times m,这一题的 m=nm = n),计算最大最小值。

1256017160161721210211222\begin{matrix} 1 & 2 & 5 & 6 \\ 0 & 17 & 16 & 0 \\ 16 & 17 & 2 & 1 \\ 2 & 10 & 2 & 1 \\ 1 & 2 & 2 & 2 \end{matrix}

为了求出 (2,2)\left(2, 2 \right)(3,3)\left(3, 3 \right) 这段区间的最大最小值:

1256017160161721210211222\begin{matrix} 1 & 2 & 5 & 6 \\ 0 & \colorbox{RoyalBlue}{\color{Red}{17}} & \colorbox{RoyalBlue}{\color{Red}{16}} & 0 \\ 16 & \colorbox{RoyalBlue}{\color{Red}{17}} & \colorbox{RoyalBlue}{\color{Red}{2}} & 1 \\ 2 & 10 & 2 & 1 \\ 1 & 2 & 2 & 2 \end{matrix}

我们需要分别知道 (2,2)\left(2, 2\right)(2,3)\left(2, 3\right) 的最大最小值,与 (3,2)\left(3, 2\right)(3,3)\left(3, 3\right) 的最大最小值即可。

1256017160161721210211222\begin{matrix} 1 & 2 & 5 & 6 \\ 0 & \colorbox{Orange}{\color{Red}{17}} & \colorbox{Orange}{\color{Red}{16}} & 0 \\ 16 & \colorbox{Purple}{\color{Red}{17}} & \colorbox{Purple}{\color{Red}{2}} & 1 \\ 2 & 10 & 2 & 1 \\ 1 & 2 & 2 & 2 \end{matrix}

将样例的进行每一行的单调队列处理之后的结果:

maxrowi,jmaxx(in,i](numx,j)maxrow:025601717160171720101020222max_{row_{i, j}} \gets \max_{x \in \left(i - n, i\right]}\left(num_{x, j}\right) \newline max_{row}: \quad \begin{matrix} 0 & 2 & 5 & 6 \\ 0 & 17 & 17 & 16 \\ 0 & 17 & 17 & 2 \\ 0 & 10 & 10 & 2 \\ 0 & 2 & 2 & 2 \end{matrix}

maxrowi,jminx(in,i](numx,j)minrow:0125001600162102210122max_{row_{i, j}} \gets \min_{x \in \left(i - n, i\right]}\left(num_{x, j}\right) \newline min_{row}: \quad \begin{matrix} 0 & 1 & 2 & 5 \\ 0 & 0 & 16 & 0 \\ 0 & 16 & 2 & 1 \\ 0 & 2 & 2 & 1 \\ 0 & 1 & 2 & 2 \end{matrix}

在此基础上构建每一列的滑动窗口:

maxcolumni,jmaxx(jn,j](maxrowi,x)maxcolumn:000001717160171716017172010102max_{column_{i, j}} \gets \max_{x \in \left(j - n, j\right]}\left(max_{row_{i, x}}\right) \newline max_{column}: \quad \begin{matrix} 0 & 0 & 0 & 0 \\ 0 & 17 & 17 & 16 \\ 0 & 17 & 17 & 16 \\ 0 & 17 & 17 & 2 \\ 0 & 10 & 10 & 2 \end{matrix}

mincolumni,jminx(jn,j](minrowi,x)mincolumn:00000020002002210121min_{column_{i, j}} \gets \min_{x \in \left(j - n, j\right]}\left(min_{row_{i, x}}\right) \newline min_{column}: \quad \begin{matrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 2 & 2 & 1 \\ 0 & 1 & 2 & 1 \end{matrix}

所以 ans 的结果:

ansi,jmaxcolumni,jmincolumni,jans:0000017151601715160151510981ans_{i,j} \gets max_{column_{i, j}} - min_{column_{i, j}} \newline ans: \quad \begin{matrix} 0 & 0 & 0 & 0 \\ 0 & 17 & 15 & 16 \\ 0 & 17 & 15 & 16 \\ 0 & 15 & 15 & 1 \\ 0 & 9 & 8 & 1 \end{matrix}

所以二维滑动窗口简要步骤如下:

  1. 先对二维的其中一维进行滑动窗口处理。
  2. 接着在另一维对已经处理过的那一维进行再次处理。

code:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <climits>
#include <deque>
#include <iostream>

using namespace std;

const int32_t MAX_A = 1000 + 10;

class Num {
public:
int32_t id;
int32_t val;
Num(const int32_t id, const int32_t val) {
this->id = id;
this->val = val;
}
};

int32_t a, b, n;

int32_t ability[MAX_A][MAX_A];
int32_t preMaxLine[MAX_A][MAX_A], preMinLine[MAX_A][MAX_A];
int32_t preMaxCol[MAX_A][MAX_A], preMinCol[MAX_A][MAX_A];

int32_t ans = INT32_MAX;
deque<Num> deq[2]; // 0max 1min

int main() {
ios::sync_with_stdio(false);

cin >> a >> b >> n;
for (int32_t i = 1; i <= a; ++i) {
for (int32_t j = 1; j <= b; ++j) {
cin >> ability[i][j];
}
}

Num tmp = Num(0, 0);
for (int32_t i = 1; i <= a; ++i) {
deq[0].clear();
deq[1].clear();
for (int32_t j = 1; j <= b; ++j) {
tmp = Num(j, ability[i][j]);

while (deq[0].size() && (ability[i][j] >= deq[0].back().val)) {
deq[0].pop_back();
}
while (deq[1].size() && (ability[i][j] <= deq[1].back().val)) {
deq[1].pop_back();
}

deq[0].push_back(tmp);
deq[1].push_back(tmp);

while ((j - n) >= deq[0].front().id) {
deq[0].pop_front();
}
while ((j - n) >= deq[1].front().id) {
deq[1].pop_front();
}

if (j >= n) {
preMaxLine[i][j] = deq[0].front().val;
preMinLine[i][j] = deq[1].front().val;
}
}
}

Num tmpMax = Num(0, 0), tmpMin = Num(0, 0);
for (int32_t j = 1; j <= b; ++j) {
deq[0].clear();
deq[1].clear();
for (int32_t i = 1; i <= a; ++i) {
tmpMax = Num(i, preMaxLine[i][j]);
tmpMin = Num(i, preMinLine[i][j]);

while (deq[0].size() && (preMaxLine[i][j] >= deq[0].back().val)) {
deq[0].pop_back();
}
while (deq[1].size() && (preMinLine[i][j] <= deq[1].back().val)) {
deq[1].pop_back();
}

while (deq[0].size() && ((i - n) >= deq[0].front().id)) {
deq[0].pop_front();
}
while (deq[1].size() && ((i - n) >= deq[1].front().id)) {
deq[1].pop_front();
}

deq[0].push_back(tmpMax);
deq[1].push_back(tmpMin);

if (i >= n) {
preMaxCol[i][j] = deq[0].front().val;
preMinCol[i][j] = deq[1].front().val;
}
}
}

for (int32_t i = n; i <= a; ++i) {
for (int32_t j = n; j <= b; ++j) {
ans = min(ans, (preMaxCol[i][j] - preMinCol[i][j]));
}
}

cout << ans << endl;

return 0;
}

最后再来亿点点练习

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