单调队列

发表于

单调队列，即单调递增或递减的队列

同时，它也被称为双端队列，就是说它不同于一般的队列只能在队首删除，队尾插入，它能在队首队尾同时删除

以维护单调递减队列为例

为保证队列的递减性，在插入元素v时，要与队尾元素比较。

如果队尾元素不大于v，删除队尾元素，然后v继续与新的队尾元素比较，直到队尾的元素大于v，这个时候才将v插入队列

单调队列，保持元素单调性的同时，也能及时排除不可能解，从而满足动态规划的最优性要求，优化动态规划算法

例1

原题地址

题目描述

输入一个长度为n的整数序列，从中找出一段不超过M的连续子序列，使得整个序列的和最大。

输入格式

第一行两个数n,m(n<=3000, m<=n)

第二行有n个数，要求在n个数找到最大子序和

输出格式

一个数，数出他们的最大子序和

样例

1
2
3
4
5
6
输入 
6 4 
1 -3 5 1 -2 3

输出
7

说明

m≤n≤3000

解析

利用前缀和做差求区间和

枚举右端点i，问题就是找到一个左端点 k,i-m<=k<=i-1使s[k]最小

(这样s[i]-s[k]才能更大)

通过分析可知，可能成为最优解的序列一定满足

下标位置递增，对应的前缀和S递增

  1. 随着右端点变从前向后扫描，对某个i执行操作

  2. 判断对头元素与i的距离是否超过m，超出则出队

  3. 此时队首就是右端点为i时，左端点为k的最优选择
  4. 不断删除队尾元素，直到对应的S值小于S[i],然后把i 作为一个新的决策入队

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,ans;
int sum[3003],a[3003],q[3003];
int l=1,r=1;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	q[1]=0;
	for(int i=1;i<=n;++i){
		while(l<=r&&q[l]<i-m)++l;
		ans=max(ans,sum[i]-sum[q[l]]);
		while(l<=r&&sum[q[r]]>=sum[i])--r;
		q[++r]=i;
	}
	printf("%d",ans);
	return 0;
}

例2

原题地址

题目描述

kkk做了一个人体感觉分析器。每一天，人都有一个感受值Ai，Ai越大，表示人感觉越舒适。在一段时间[i, j]内，人的舒适程度定义为[i, j]中最不舒服的那一天的感受值 * [i, j]中每一天感受值的和。现在给出kkk在连续N天中的感受值，请问，在哪一段时间，kkk感觉最舒适？

输入格式

第一行为N，代表数据记录的天数

第二行N个整数，代表每一天的感受值

输出格式

一行，表示在最舒适的一段时间中的感受值

样例

1
2
3
4
5
6
输入
6
3 1 6 4 5 2

输出
60

说明

样例解释：

kkk最开心的一段时间是第3天到第5天，开心值：(6+4+5)*4=60

对于30%的数据，1<=N<=100

对于70%的数据，1<=N<=2000

对于100%的数据，1<=N<=100000，1<=感受值<=1000000

解析

这个题的数据范围规定没有负数，所以前缀和绝对是会越来越大的，所以队中元素应该是那个最不舒服的值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
int n;
long long a[100005],q[100005],sum[100005],f[100005],tail,ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n+1;++i){
		while(a[q[tail]]>a[i]){
			f[q[tail]]+=(sum[i-1]-sum[q[tail]]);
			tail--;
		}
		f[i]=sum[i]-sum[q[tail]];
		q[++tail]=i;
	}
	for(int i=1;i<=n;++i)ans=max(ans,f[i]*a[i]);
	cout<<ans;
}