单调队列

学习
字数统计: 2.9k   |   阅读时长≈ 13 分钟

单调队列

推荐学习视频：C15【模板】单调队列 滑动窗口最值_bilibili

0. 概述

  • 用于求滑动窗口内的最小值和最大值

1. 单调队列

  • 队尾进队出队，队头出队（维护子序列的单调性）的数据结构
  • 队尾出队的条件：队列不空且新元素更优，队中旧元素队尾出队
  • 每个元素必然从队尾进队一次
  • 队头出队的条件：队头元素滑出了窗口
  • 注意：队列中存储元素的下标，方便判断队头出队

image-20240327125322278

1.1. 维护滑动窗口的最大值/最小值

  • 基于数组
1
2
3
4
5
6
7
8
9
10
11
int h=1,t=0; // 当队尾t<队头h时,说明单调队列中没有元素
for(int i=1;i<=n;i++) {
    // 当前队头q[h]不在窗口[i-k+1,i]内,队头出队
    if(h<=t && q[h]<i-k+1) h++;
    // 当前值>=队尾值,队尾出队(如果当前值比队头还大,那么会一直出队到队头出队)
    while(h<=t && a[i]>=a[q[t]]) t--;
    // 当前值从队尾入队,注意入队的是下标,一直存储的都是下标
    q[++t]=i;
    // 如果i>=k表明起码占满一个窗口,此时队头中的是最大值
    if(i>=k) cout<<a[q[h]]<<' ';
}

题目链接：P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e6+5;
int a[N],q[N]; // q是队列,建议数组模拟,不开O2优化的情况下数组都比STL库更快

int main() {
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
	}
	// 维护窗口最小值O(n)
	int h=1,t=0; // 当队尾t<队头h时,说明单调队列中没有元素
	for(int i=1;i<=n;i++) { // 枚举队列中所有元素
		// 新元素比当前队尾还小,说明新元素更优,那么把后面的全部移出去,最小的变进来
		while(h<=t && a[q[t]]>=a[i]) t--;
		q[++t]=i; // 注意,q存的都是下标嗷,表示把i从队尾入队
		// 当新元素不是最优时,也会直接执行q[++t]=i加到当前窗口的末尾
		if(q[h]<i-k+1) h++; // i-k+1是当前窗口的左边界,如果队头下标小于i-k+1,说明窗口右移
		// 此时相当于队头出队
		if(i>=k) cout<<a[q[h]]<<' '; // 能输出第一个窗口的大小时
	}
	cout<<endl;
	// 维护最大值的单调队列,q[h]代表队头元素的下标
	h=1,t=0;
	for(int i=1;i<=n;i++) {
		// 如果比队尾更优,则出队
		while(h<=t && a[q[t]]<=a[i]) t--;
		// 入队
		q[++t]=i;
		// 滑动窗口右移
		if(q[h]<i-k+1) h++;
		// 输出当前窗口最大值
		if(i>=k) cout<<a[q[h]]<<' ';
	}
	return 0;
}

  • 基于STL

  • 单调队列是相较于队列，队头也可以出队的数据结构，则可以用 $STL$ 库中的 $deque$ 实现【双端队列，可以入队也可以出队】

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=n;i++) {
    // 输出最小值,a[i]比队尾元素更优,则弹出对位并加入队列
    // 如果dq不为空且这个新元素更优,则去尾
    while(!dq.empty() && a[dq.back()]>a[i]) dq.pop_back(); // 去尾
    dq.push_back(i); // 1)去尾后将最优元素加入到队列中;2)dq为空,自然将下标入队;3)
    // 如果达到窗口大小
    if(i>=k) {
        // 如果dq不为空并且队头元素下标小于等于i-k(即滑出窗口了)
        while(!dq.empty() && dq.front()<=i-k) dq.pop_back(); // 删头
        printf("%d ",a[dq.front()]); // 输出队头的元素,此时对应最大值
    }
}

题目链接：P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

  • 要 $pop_back()$ 或者 $pop_front()$ 之前可以用 $dq.size()$ 检测一下是否有元素，否则可能导致 $RE$
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
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: RE也可能是数组没开够哦

const int N=1e6+5;
int a[N];
deque<int> dq; // 双端队列表示单调队列
int n,k; // 元素个数以及窗口大小

int main() {
	cin>>n>>k;
	for(int i=1;i<=n;i++) {
		cin>>a[i];	
	}
	// 找最小值
	for(int i=1;i<=n;i++) {
		// 输出最小值,a[i]比队尾元素更优,则弹出对位并加入队列
		// 如果dq不为空且这个新元素更优,则去尾
		while(!dq.empty() && a[dq.back()]>a[i] && dq.size()) dq.pop_back(); // 去尾
		dq.push_back(i); // 1)去尾后将最优元素加入到队列中;2)dq为空,自然将下标入队;3)
		// 如果达到窗口大小
		if(i>=k) {
			// 如果dq不为空并且队头元素下标小于等于i-k(即滑出窗口了)
			while(!dq.empty() && dq.front()<=i-k && dq.size()) dq.pop_front(); // 删头
			printf("%d ",a[dq.front()]); // 输出队头的元素,此时对应最大值
		}
	}
	cout<<endl;
	dq.clear();
	// 找最大值,如果a[i]比队尾大就入队
	for(int i=1;i<=n;i++) {
		while(!dq.empty() && a[dq.back()]<a[i] && dq.size()) dq.pop_back();
		dq.push_back(i);
		if(i>=k) {
			while(!dq.empty() && dq.front()<=i-k && dq.size()) dq.pop_front();
			printf("%d ",a[dq.front()]);
		}
	}
	return 0;
}

1.2. 维护连续子序列的最大和

题目链接：

  • 基于数组

  • 给定一个长度为n的整数序列，请找出长度不超过 $m$ 的连续子序列的最大和。例如，数组 ${2,\ -3,\ 5,\ 2,\ -4,\ -1,\ 8}$ ，$m$ 取 $3$ ，那么长度不超过 $3$ 的连续子序列的最大和为 $8$

image-20240327145503331

  • 对于常规做法（左边），每次枚举一个窗口长度，再在这个窗口中枚举得到最大的连续子段和，时间复杂度是 $O(n^3)$，对于右图，表示的是前缀和数组 $s$
  • 对于连续子段和（区间和），我们很容易想到预处理一个前缀和数组，这样就可以把计算连续字段和的时间从 $O(n)$ 优化到 $O(1)$，$i$ 到 $j$ 的间和计算公式是 $s[i]-s[j-1]$，我们只要找到左端点 $s[l-1]$ 的最小值，那么就可以求出 $s[i]-min(s[j]),\ j∈[i-m,i-1]$ 得到前 $i$ 项的最大连续子段和，因为要枚举求得最小值，所以时间复杂度是 $O(n^2)$
  • 但是，如果我们再用单调队列维护这个最小值，就不需要再枚举求连续区间和的最小值，时间复杂度会继续下降到 $O(n)$
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
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e5+5;
int a[N];
int q[N]; // 单调队列
int s[N]; // 前缀和序列

int main() {
	int n,k;
	cin>>n>>k; // 求的是长度不超过k的最大区间和
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);	
		s[i]=s[i-1]+a[i];
	}
	int h=0,t=0;
	q[0]=0;
	int ans=s[1]; // 初始化区间和的答案

	for(int i=1;i<=n;i++) {
		// 队头不在窗口[i-k,i-1]内,队头出队
		if(h<=t && q[h]<i-k) h++; // 这里因为只用看前i-k个元素,窗口右边界小了1,因此不用加1
		// 使用队头最小值,同样的因为队尾小了1,所以要把最小值在这里处理
		ans=max(ans,s[i]-s[q[h]]);
		// 当前值<=队尾值,队尾出队,把更小的s[i]放进队列中以维护s[i]的最小值
		while(h<=t && s[i]<=s[q[t]]) t--;
		// 从队尾正常入队
		q[++t]=i; // 放进去的仍然是下标哈
	}
	cout<<ans<<endl;
	return 0;
}
/*
Input:
7 3
2 -3 5 2 -4 -1 8
Output:
8
/*
  • 另一种写法，本人暂时还没验证是否正确，在维护滑动窗口最大值和最小值的基础上只改动了最后一步，即维护 $ans$ 的代码，因为 $s[i]-s[q[h]]$ 中 $s[q[h]]$ 已经前 $i$ 项窗口大小为 $[1,k]$ 的滑动窗口中前缀和的最小值，所以相减即可得到最大区间和
1
2
3
4
5
6
7
8
int ans=s[1];
h=1,t=0;
for(int i=1;i<=n;i++) {
    while(h<=t && s[i]<=s[q[t]]) t--;
    q[++t]=i;
    if(h<=t && q[h]<i-k) h++;
    ans=max(ans,s[i]-s[q[h]]);
}
  • 如果窗口大小是从 $[st,en]$（用户手动输入），那么模板可改为：
1
2
3
4
5
6
7
8
9
10
11
int h=1,t=0;
// 枚举每个元素
for(int i=1;i<=n;i++) {
    // 对于区间长度在[st,en]之间,当i>=st才计算
    if(i>=st) { 
        while(h<=t && s[i-st]<=s[q[t]]) t--;
        q[++t]=i-st; // 偏移量是i-st
    }
    if(h<=t && q[h]<i-en) h++;
   	ans=max(ans,s[i]-s[q[h]]);
}

  • 基于STL

  • 关键点，$dq.fonrt()<i-k$ 此时代表窗口大于 $k$ 了，因为窗口大小是 $≤k$ 所以没有设限 $if(i>=k)$

  • 对于 $dq.empty()$ 即是最初的状态，即没有任何元素，此时只会添加 $s[1]$ 进去，其他情况会进入 $s[i]-s[dq.front()]$ 表示 $[0,i-1]$ 中的最小值

1
2
3
4
5
6
7
8
9
10
11
int ans=INT_MIN; // 找最大值
dq.push_back(0); 
// 枚举到第i个元素,则从前[0,i-1]中找最小值s[j](前缀和),用s[i]-s[j]即可
for(int i=1;i<=n;i++) {
    // 因为窗口大小是小于等于k,所以一旦dq.front<i-k代表窗口大小大于k了
    while(!dq.empty() && dq.front()<i-k) dq.pop_front(); // 删头
    if(dq.empty()) ans=max(ans,s[i]); // 对应最初状态,这里只会添加s[1],其他情况下队列起码有一个元素
    else ans=max(ans,s[i]-s[dq.front()]); // 此时dq中的是0~s[i-1]中的最小值
    while(!dq.empty() && dq.back()>=s[i]) dq.pop_back();
    dq.push_back(i);
}
  • 完整代码
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
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e5+5;
int a[N];
int s[N]; // 前缀和
deque<int> dq; // 单调队列
int n,k; // 长度不超过k的子序列最大和

int main() {
	cin>>n>>k;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	int ans=INT_MIN; // 找最大值
	dq.push_back(0); 
	// 枚举到第i个元素,则从前[0,i-1]中找最小值s[j](前缀和),用s[i]-s[j]即可
	for(int i=1;i<=n;i++) {
		// 因为窗口大小是小于等于k,所以一旦dq.front<i-k代表窗口大小大于k了
		while(!dq.empty() && dq.front()<i-k) dq.pop_front(); // 删头
		if(dq.empty()) ans=max(ans,s[i]); // 对应最初状态,这里只会添加s[1],其他情况下队列起码有一个元素
		else ans=max(ans,s[i]-s[dq.front()]); // 此时dq中的是0~s[i-1]中的最小值
		while(!dq.empty() && dq.back()>=s[i]) dq.pop_back();
		dq.push_back(i);
	}
	cout<<ans;
	return 0;
}
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信