llxyyq @ 2016-11-29 18:29:57
#include<iostream>
#include<cstdio>
using namespace std;
int n,k;
int a[1000006],b[1000006];
int head,tail ;
//void pri(){
// int i;
// printf("队列");
// for(i=head;i<=tail;i++)
// printf("%d ",a[b[i]]);
// printf("\n");
// printf("坐标");
// for(i=head;i<=tail;i++)
// printf("%d ",b[i]);
// printf("\n");
//}
int main(){
int i;
scanf("%d %d",&n,&k);
for(i=0;i<=n-1;i++)
scanf("%d",&a[i]);
head=0;
tail=0;
b[0]=0;
i=0;
while(i<n-1){
i++;
while(head<=tail&&a[b[tail]]>a[i]) tail--;
b[++tail]=i;
if(tail-head+1>k)
head++;
while(head<=tail&&b[head]<=i-k) head++;
//pri();
if(i>=k-1)
printf("%d ",a[b[head]]);
}
printf("\n");
i=0;
head=0;
tail=0;
b[0]=0;
while(i<n-1){
i++;
while(head<=tail&&a[b[tail]]<a[i]) tail--;
b[++tail]=i;
if(head-tail+1>k)
head++;
while(head<=tail&&b[head]<=i-k) head++;
if(i>=k-1)
printf("%d ",a[b[head]]);
}
return 0;
}
by DeskalLorll @ 2016-11-29 18:59:12
用单调队列吧