poj2823Sliding Window

#include<iostream> #include<cstdio> using namespace std; int n,k,a[1000005],mx[1000005],mn[1000005]; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } int l=0,r=0; for(int i=1;i<=n;i++) { while(l<=r&&a[i]<=a[mn[r]])r--; mn[++r]=i; while(l<r&&mn[r]-mn[l]>=k)l++; if(i>=k)printf("%d ",a[mn[l]]); } l=0;r=0; printf("\n"); for(int i=1;i<=n;i++) { while(l<=r&&a[i]>=a[mx[r]])r--; mx[++r]=i; while(l<r&&mx[r]-mx[l]>=k)l++; if(i>=k)printf("%d ",a[mx[l]]); } return 0; }

，