给定一个长度为n的数列a，再给定一个长度为k的滑动窗口，从第一个数字开始依次框定k个数字，求每次框定的数字中的最大值和最小值，依次输出所有的这些值。下面有一个例子数组是 [1 3 1 3 5 6 7] , k 是3：
窗口位置 窗口中的最小值 窗口中的最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7第一行包含两个整数 n 和 k ，分别表示数组的长度和滑动窗口长度。
第二行n个整数，表示数列元素的值。
第一行从左到右窗口看到的最小值。
第二行从左到右窗口看到的最大值。
8 3
1 3 -1 -3 5 3 6 7-1 -3 -3 -3 3 3
3 3 5 5 6 7时间：1s 空间：64M
30%：n<=100 k<=20
60%：n<=5000 k<=20
100%：n<=10^6，每个元素不操过int类型
需要读入输出优化
谁说要读入输出优化的？？？
#include<cstdio> #include<iostream> using namespace std; int n,k,i,j,a[1000005],ans1=2147483647,ans2=-2147483646,m=1; struct node{ int x,y; }ch[1000005]; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)w=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) s=s*10+ch-‘0‘,ch=getchar(); return s*w; } int main(){ n=read(); k=read(); for(i=1;i<=n;i++){ a[i]=read(); } if(k>=n){ for(i=1;i<=n;i++){ if(a[i]<ans1){ ans1=a[i]; } if(a[i]>ans2){ ans2=a[i]; } } printf("%d\n%d",ans1,ans2); return 0; } for(i=1;i<=k;i++){ if(a[i]<ans1){ ans1=a[i]; } if(a[i]>ans2){ ans2=a[i]; } } ch[1].x=ans1; ch[1].y=ans2; for(i=1;i+k<=n;i++){ if((a[i]==ans1)||(a[i]==ans2)){ ans1=214748364; ans2=-214748364; for(j=1;j<=k;j++){ if(a[j+i]<ans1){ ans1=a[j+i]; } if(a[j+i]>ans2){ ans2=a[j+i]; } } } if(a[k+i]<ans1){ ans1=a[k+i]; } if(a[k+i]>ans2){ ans2=a[k+i]; } ch[++m].x=ans1; ch[m].y=ans2; } for(i=1;i<=m;i++){ printf("%d ",ch[i].x); } printf("\n"); for(i=1;i<=m;i++){ printf("%d ",ch[i].y); } return 0; }
原文：https://www.cnblogs.com/hrj1/p/11191926.html