动态规划（算法竞赛、蓝桥杯）--单调队列滑动窗口与连续子序列的最大和

1、B站视频链接：E11【模板】单调队列 滑动窗口最值_哔哩哔哩_bilibili

题目链接：滑动窗口 /【模板】单调队列 - 洛谷

#include <bits/stdc++.h> 
using namespace std;
const int N=1000010;
int a[N],q[N];//q存的是元素的下标 

int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	
	//维护窗口最小值
	int h=1,t=0;//清空队列且t在h之前
	for(int i=1;i<=n;i++){
		while(h<=t&&a[i]<=a[q[t]])t--;//队尾出队（队列不空且新元素更优
		q[++t]=i;//队尾入队(存储下标 方便判断队头出队)
		if(q[h]<i-k+1)h++;//队头出队滑出了窗口
		if(i>=k)printf("%d ",a[q[h]]);//使用最值 
	} 
	puts("");
	//维护窗口最大值
	h=1,t=0;
	for(int i=1;i<=n;i++){
		while(h<=t&&a[i]>=a[q[t]])t--;
		q[++t]=i;
		if(q[h]<i-k+1)h++;
		if(i>=k)printf("%d ",a[q[h]]);
	}
	return 0;
}

练习题：1、求m区间内的最小值 - 洛谷

2、扫描 - 洛谷    3、 [HAOI2007] 理想的正方形 - 洛谷

2、B站视频链接：E12 单调队列 连续子序列的最大和_哔哩哔哩_bilibili

#include <bits/stdc++.h> 
using namespace std;
const int N=300010;
int n,m;
int s[N],f[N],q[N];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&s[i]),s[i]+=s[i-1];//前缀和 
	}
	int h=1,t=0;//清空队列
	for(int i=1;i<=n;i++){//枚举序列 
		while(h<=t&&s[i-1]<=s[q[t]])t--;//队尾出队（队尾不空且更优）		 
		q[++t]=i-1;//队尾入队，存储下标
		if(q[h]<i-m)h++;//队头出队滑出窗口
		f[i]=s[i]-s[q[h]]; 
	}
	int res=-2e9;
	for(int i=1;i<=n;i++){
		res=max(res,f[i]);
	} 
	printf("%d\n",res);
	return 0;
}