经典例题：滑动窗口

维护一个存放候选答案（实际上存放的是答案的下标）的队列，队列中的值都有可能（或早或晚，除非窗口已经滑到末尾）被当作窗口中的最小值被输出，每次输出都是以队列的 front 作为窗口中的最小值。

通过分析发现，如果a[i] >= a[i+1]，那么当a[i+1] 存在的时候，总是输出a[i+1]而忽略a[i]，也就是说当后一个数比前一个数更小（或相等），后一个数更具优势，只要窗口种包含后一个数，前一个数就一定不会被输出，那么就先将a[i]先弹出，然后再将a[i+1]加进去，由此可看出，从现在开始一直到a[i]移除窗口，a[i]都永无出头之日，所以a[i]不可能会被输出，那么就不应该被存放在队列中，这也和之前说的队列中存放的元素是答案候选相对应。
考虑样例：1 3 -1 -3 5 3 6 7
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
1 3 -1 -3 5 3 6 7
（Ps: que存储下标，但为了形象，就直接写值了）

i=0:
que: 1

i=1:
que: 1, 3

i=2:
由于a[2]<a[1], a[2] < a[0]
于是先pop+pop，再push
que: -1
ans: -1

i=3:
que: -3
ans: -3

i=4:
que: -3, 5
ans: -3

i=5:
que: -3, 3
ans: -3

i=6:
由于窗口长度为3，a[3]=-3已经被移出
que: 3, 6
ans: 3

i=7:
que: 3, 6, 7
ans: 3

6,7由于窗口已经滑到末尾，故不再输出

1. include [HTML_REMOVED]

2. include [HTML_REMOVED]

3. define N 1000010

4. include [HTML_REMOVED]

5. using namespace std;  
7. int n, m;  
8. int a[N];  
9. int que[N];  
10. int head, tail = -1;  
12. int main()  
13. {  
14. cin >> n >> m;  
16. for (int i = 0; i < n; i ++) scanf(“%d”, a + i);  
18. for (int i = 0; i < n; i ++)  
19. {  
20. if(head <= tail && i - que[head] >= m) head ++;   
21. // 判断que.front()是否已经滑出窗口  
22. // 事实上head <= tail的判断条件可以不用加，但是加上是一个好习惯  
24. while(head <= tail && a[que[tail]] >= a[i]) tail –;   
25. que[++ tail] = i;  
26. // 优势元素入队，劣势元素出队（尾部操作）  
28. if(i >= m - 1){  
29. printf(“%d”, a[que[head]]); // 每次将队首元素当作ans输出  
30. if(i != n - 1) printf(” ”);  
31. else puts(“”);  
32. }  
33. }  
35. head = 0, tail = -1;  
36. for (int i = 0; i < n; i ++)  
37. {  
38. if(head <= tail && i - que[head] >= m) head ++;   
39. // 判断que.front()是否已经滑出窗口  
40. while(head <= tail && a[que[tail]] <= a[i]) tail –;  
41. que[++ tail] = i;  
43. if(i >= m - 1){  
44. printf(“%d”, a[que[head]]);//每次将队首元素当作ans输出  
45. if(i != n - 1) printf(” ”);  
46. else puts(“”);  
47. }  
48. }  
49. }