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;
}

?

?