滑动窗口，就是有一个区间，当区间长度大于k时，就pop该区间的首元素，这满足先进先出的条件，那么我们可以用一个队列来维护这个区间
1. #include<iostream> 2. using namespace std; 3. const int N=1000010; 4. int a[N],queue[N]; 5. int n,k; 6. 7. int main(void) 8. { 9. scanf("%d %d",&n,&k); 10. for(int i=0;i<n;i++) scanf("%d",&a[i]); 11. int hh=0,tt=-1;//hh为队头，tt为队尾 12. for(int i=0;i<n;i++) 13. { 14. if(hh<=tt&&i-k+1>queue[hh])//判断是否需要滑动窗口，pop队头 15. { 16. hh++; 17. } 18. while(hh<=tt&&a[i]<a[queue[tt]])//判断队列末尾是否满足单调性 19. { 20. tt--; 21. } 22. queue[++tt]=i; 23. if(i-k+1>=0) printf("%d ",a[queue[hh]]);//如果滑动窗口满足k，可进行输出 24. } 25. printf("\n"); 26. hh=0,tt=-1; 27. for(int i=0;i<n;i++) 28. { 29. if(hh<=tt&&i-k+1>queue[hh]) 30. { 31. hh++; 32. } 33. while(hh<=tt&&a[i]>a[queue[tt]]) 34. { 35. tt--; 36. } 37. queue[++tt]=i; 38. if(i-k+1>=0) printf("%d ",a[queue[hh]]); 39. } 40. return 0; 41. }
变式:
1. #include<iostream> 2. using namespace std; 3. const int N = 5000010; 4. int a[N], queue[N]; 5. int n, m; 6. 7. int main(void) 8. { 9. scanf("%d %d", &n, &m); 10. for (int i = 0; i < n; i++) scanf("%d", &a[i]); 11. int hh = 0, tt = -1; 12. for (int i = 0; i < n; i++) 13. { 14. if (hh <= tt && i - m> queue[hh])hh++; 15. while (hh <= tt && a[i] < a[queue[tt]])tt--; 16. if (i>= 1)printf("%d\n", a[queue[hh]]); 17. else printf("0\n"); 18. queue[++tt] = i; 19. } 20. return 0; 21. }
