ps:遗忘了原理,可以参考下文
https://www.acwing.com/solution/content/2499/
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #define INF 0x3f3f3f3f using namespace std; const int N=1e6; int n,k; int head,tail,p[N],q[N],a[N]; void get_max(){ head=1,tail=0; for(int i=1;i<=n;i++){ while(head<=tail&&q[tail]<=a[i]) tail--; q[++tail]=a[i]; p[tail]=i; while(p[head]<=i-k) head++; if(i>=k) printf("%d ",q[head]); } printf("\n"); } void get_min(){ head=1,tail=0; for(int i=1;i<=n;i++){ while(head<=tail&&q[tail]>=a[i]) tail--; q[++tail]=a[i]; p[tail]=i; while(p[head]<=i-k) head++; if(i>=k) printf("%d ",q[head]); } printf("\n"); } int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); get_min(); get_max(); return 0; }