一些小记录
1.队列里存的是a[i]的下标即i
2.head出队,tail入队和出队
输出结果时head出队,输入时tail入队
a[q[tail]]的值比a[i]差时则tail–出队
例如:求最小值时,a[q[tail]]>=a[i],tail–出队
3.每个i都会入队一次
代码
#include<iostream>
using namespace std;
/*
队列里存的是a[i]的下标即i
head出队,tail入队和出队
a[q[tail]]的值比a[i]差时则tail--出队
每个i都会入队一次
*/
const int N=1000010;
int a[N],q[N];
int head=0,tail=-1;
int main(){
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
//最小值
for(int i=0;i<n;i++){
//head<=tail表示队列不为空
if(head<=tail&&i>=q[head]+k) head++;//i>=q[head]+k,说明超出了窗口,head出队
while(head<=tail&&a[i]<a[q[tail]]) tail--;//a[i]中的值比a[q[tail]好,则a[q[tail]]出队
q[++tail]=i;
if(i>=k-1) cout<<a[q[head]]<<" ";
}
cout<<endl;
head=0,tail=-1;
//最大值
for(int i=0;i<n;i++){
if(head<=tail&&i>=q[head]+k) head++;
while(head<=tail&&a[i]>a[q[tail]]) tail--;//a[i]中的值比a[q[tail]好,则a[q[tail]]出队
q[++tail]=i;
if(i>=k-1) printf("%d ",a[q[head]]);
}
return 0;
}