长度为N的数组，求宽度k的滑动窗口在数组上滑动时窗口内的最大值或最小值
如果用单调队列做，求最小值时，队列应该严格递增的。所以插入时，队尾大于等于插入值的元素都应被舍弃，因为插入元素不仅小而且新，没有必要保留队尾这些又大又旧的元素。
/*
选C++交是5k多毫秒，但是G++就会超时。
*/
#include <cstdio>
#include <cstring>
const int N = ;
int data[N];
int o1[N],o2[N];
int q[N];
int n,k;
void getMin(){
int head,tail;
head = tail = ;
for(int i=;i<n;i++){
while((tail>head)&&data[q[tail-]]>data[i]) tail--;
q[tail++] = i;
if(i>=(k-)){
while((head<tail)&&q[head]<(i-k+)) head++;
o1[i-k+] = data[q[head]];
}
}
}
void getMax(){
int head,tail;
head = tail = ;
for(int i=;i<n;i++){
while((head<tail)&&(data[q[tail-]]<data[i])) tail--;
q[tail++] = i;
if(i>=(k-)){
while((head<tail)&&(q[head]<(i-k+))) head++;
o2[i-k+] = data[q[head]];
}
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=;i<n;i++) scanf("%d",data+i);
getMin();
getMax();
for(int i=;i<n-k+;i++) printf("%d ",o1[i]); puts("");
for(int i=;i<n-k+;i++) printf("%d ",o2[i]); puts("");
return ;
}
长度为N的数组，长度小于等于K的非空子串的最大和。
求完前缀和后就转化成了窗宽为k的单调队列
#include <cstdio>
#include <cstring>
const int N = ;
const int INF = 0x0FFFFFFF;
int data[N],sum[N*];
int q[N*];
int n,k,total;
int minq(int &spos,int &epos){
int head,tail;
head = tail = ;
int ans = -INF;
for(int i=;i<total;i++){
while((head<tail)&&(sum[q[tail-]]>=sum[i-])) tail--;
while((head<tail)&&q[head]<i-k) head++;
q[tail++] = i-;
if((sum[i]-sum[q[head]]>ans)){
spos = q[head];
epos = i;
ans = sum[epos]-sum[spos];
}
}
return ans;
}
int main(){
int t;
for(scanf("%d",&t);t--;){
scanf("%d%d",&n,&k);
sum[] = ;
for(int i=;i<=n;i++){
scanf("%d",data+i);
sum[i]=sum[i-]+data[i];
}
for(int i=;i<k;i++) sum[n+i]=sum[n+i-]+data[i]; total = n+k;
int spos,epos;
int ans = minq(spos,epos);
spos++;
if(epos>n) epos-=n;
if(spos>n) spos-=n;
printf("%d %d %d\n",ans,spos,epos);
}
return ;
}