单调队列的实现

单调队列

也许这种数据结构的名字你没听过,其实没啥难的,就是一个「队列」,只是使用了一点巧妙的方法,使得队列中的元素单调递增(或递减)。这个数据结构有什么用?可以解决滑动窗口的一系列问题。

单调队列是一种主要用于解决滑动窗口类问题的数据结构,即,在长度为 n 的序列中,求每个长度为 n 的区间的区间最值

题目

理解

在一堆数字中,已知最值,如果给这堆数添加一个数,那么比较一下就可以很快算出最值;但如果减少一个数,就不一定能很快得到最值了,而要遍历所有数重新找最值。

回到这道题的场景,每个窗口前进的时候,要添加一个数同时减少一个数,所以想在 O(1) 的时间得出新的最值,就需要「单调队列」这种特殊的数据结构来辅助了。

一个普通的队列

1
2
3
4
5
6
7
8
class Queue
{
void push(int n);
// 或 enqueue,在队尾加入元素 n

void pop();
// 或 dequeue,删除队头元素
}

单调队列操作

1
2
3
4
5
6
7
8
9
10
11
class MonotonicQueue
{
// 在队尾添加元素 n
void push(int n);

// 返回当前队列中的最大值
int max();

// 队头元素如果是 n,删除它
void pop(int n);
}

当然,这几个 API 的实现方法肯定跟一般的 Queue 不一样,不过我们暂且不管,而且认为这几个操作的时间复杂度都是 O(1),先把这道「滑动窗口」问题的解答框架搭出来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> maxSlidingWindow(vector<int>& nums,int k)
{
MonotonicQueue window;
vector<int> res;
for(int i =0; i < nums.size(); i++)
{
if(i < k -1)
{//先把窗口的前 k - 1 填满
window.push(nums[i]);
}
else
{// 窗口开始向前滑动
window.push(nums[i]);
res.push_back(window.max());
window.pop(nums[i - k +1]);
// nums[i - k + 1] 就是窗口最后的元素
}
}
return res;
}

20210809212742

实现单调队列

首先我们要认识另一种数据结构:deque,即双端队列。很简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class deque {
// 在队头插入元素 n
void push_front(int n);
// 在队尾插入元素 n
void push_back(int n);
// 在队头删除元素
void pop_front();
// 在队尾删除元素
void pop_back();
// 返回队头元素
int front();
// 返回队尾元素
int back();
}

而且,这些操作的复杂度都是 O(1)。这其实不是啥稀奇的数据结构,用链表作为底层结构的话,很容易实现这些功能。

「单调队列」的核心思路和「单调栈」类似。单调队列的 push 方法依然在队尾添加元素,但是要把前面比新元素小的元素都删掉:

1
2
3
4
5
6
7
8
9
10
11
class MonotonicQueue{
private:
deque<int> data;
public:
void push(int n){
while(!data.empty()&& data.back()< n)
data.pop_back();
data.push_back(n);
}
};

你可以想象,加入数字的大小代表人的体重,把前面体重不足的都压扁了,直到遇到更大的量级才停住

20210809212959

如果每个元素被加入时都这样操作,最终单调队列中的元素大小就会保持一个单调递减的顺序,因此我们的 max() API 可以可以这样写:

1
2
3
int max(){
return data.front();
}

pop() API 在队头删除元素 n,也很好写:

1
2
3
4
void pop(int n){
if(!data.empty()&& data.front()== n)
data.pop_front();
}

之所以要判断 data.front() == n,是因为我们想删除的队头元素 n 可能已经被「压扁」了,这时候就不用删除了:
20210809213911

至此,单调队列设计完毕,看下完整的解题代码

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
classMonotonicQueue{
private:
deque<int> data;
public:
void push(int n){
while(!data.empty()&& data.back()< n)
data.pop_back();
data.push_back(n);
}
int max(){return data.front();}
void pop(int n){
if(!data.empty()&& data.front()== n)
data.pop_front();
}
};
vector<int> maxSlidingWindow(vector<int>& nums,int k){
MonotonicQueue window;
vector<int> res;
for(int i =0; i < nums.size(); i++){
if(i < k -1){//先填满窗口的前 k - 1
window.push(nums[i]);
}else{// 窗口向前滑动
window.push(nums[i]);
res.push_back(window.max());
window.pop(nums[i - k +1]);
}
}
return res;
}

总结

单调队列在添加元素的时候靠删除元素保持队列的单调性

时间复杂度

读者可能疑惑,push 操作中含有 while 循环,时间复杂度不是 O(1) 呀,那么本算法的时间复杂度应该不是线性时间吧?

单独看 push 操作的复杂度确实不是 O(1),但是算法整体的复杂度依然是 O(N) 线性时间。要这样想,nums 中的每个元素最多被 push_back 和 pop_back 一次,没有任何多余操作,所以整体的复杂度还是 O(N)。

空间复杂度就很简单了,就是窗口的大小 O(k)。

题目

LeetCode-滑动窗口的最大值

模板

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
int q[nums.size()], hh=0, tt=-1;
memset(q, 0, sizeof q);
for(int i=0; i<nums.size(); i++){
if(hh<=tt && q[hh]<=i-k) hh ++;
while(hh<=tt && nums[q[tt]] <= nums[i]) tt--;
q[++ tt] = i;
if(i>=k-1) res.push_back(nums[q[hh]]);
}
return res;
}
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
# include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N], hh, tt = -1;

int main()
{
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++ i)
{
scanf("%d", &a[i]);
if (i - k + 1 > q[hh]) ++ hh; // 若队首出窗口,hh加1
while (hh <= tt && a[i] <= a[q[tt]]) -- tt; // 若队尾不单调,tt减1
q[++ tt] = i; // 下标加到队尾
if (i + 1 >= k) printf("%d ", a[q[hh]]); // 输出结果
}
cout << endl;
hh = 0; tt = -1; // 重置!
for (int i = 0; i < n; ++ i)
{
if (i - k + 1 > q[hh]) ++ hh;
while (hh <= tt && a[i] >= a[q[tt]]) -- tt;
q[++ tt] = i;
if (i + 1 >= k) printf("%d ", a[q[hh]]);
}
return 0;
}
//----

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, k, q[N], a[N];//q[N]存的是数组下标
int main()
{
int tt = -1, hh=0;//hh队列头 tt队列尾
cin.tie(0);
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i = 0; i <n; i ++) cin>>a[i];
for(int i = 0; i < n; i ++)
{
//维持滑动窗口的大小
//当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)>我们设定的
//滑动窗口的大小(k),队列弹出队列头元素以维持滑动窗口的大小
if(hh <= tt && k < i - q[hh] + 1) hh ++;
//构造单调递增队列
//当队列不为空(hh <= tt) 且 当队列队尾元素>=当前元素(a[i])时,那么队尾元素
//就一定不是当前窗口最小值,删去队尾元素,加入当前元素(q[ ++ tt] = i)
while(hh <= tt && a[q[tt]] >= a[i]) tt --;
q[ ++ tt] = i;
if(i + 1 >= k) printf("%d ", a[q[hh]]);
}
puts("");
hh = 0,tt = -1;
for(int i = 0; i < n; i ++)
{
if(hh <= tt && k < i - q[hh] + 1) hh ++;
while(hh <= tt && a[q[tt]] <= a[i]) tt --;
q[ ++ tt] = i;
if(i + 1 >= k ) printf("%d ", a[q[hh]]);
}
return 0;
}