**单调队列的模板题（做很多题的前置准备）
本题我们维护一个从大到小/从小到大的单调队列即可。拿最大值来举例：对于新加进来的数，如果比队尾小我们就加进来，否则为了维护单调性我们从队尾弹出比当前值小的值。不难证明这些弹出的值不会是任何一个滑动窗口的答案。对于窗口的限定长度，我们只需要每次判断队首元素所在位置是否超过窗口长度，超过弹出即可，后输出队首（即当前队列中的最大值）即可。
代码如下：（感觉还是挺简洁易懂的）
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <queue> 5 using namespace std; 6 int q1[1000005],q2[1000005]; 7 int n,k,a[1000005]; 8 void maxx(){ 9 int head=1,t=0; 10 for (int i = 1;i <= n;i++){ 11 while(head<=t&&q1[head]+k<=i) head++;//查看队首是否超过限定长度，超过就弹出 12 while(head<=t&&a[i]>a[q1[t]]) t--;//维护单调性 13 q1[++t]=i; 14 if (i>=k) cout<<a[q1[head]]<<" "; 15 } 16 } 17 void minn(){ 18 int head=1,t=0; 19 for (int i = 1;i <= n;i++){ 20 while(head<=t&&q2[head]+k<=i) head++;//查看队首是否超过限定长度，超过就弹出 21 while(head<=t&&a[i]<a[q2[t]]) t--;//维护单调性 22 q2[++t]=i; 23 if (i>=k) cout<<a[q2[head]]<<" "; 24 } 25 } 26 int main(){ 27 scanf ("%d%d",&n,&k); 28 for (int i = 1;i <= n;i++) scanf ("%d",&a[i]); 29 minn(); 30 cout<<endl; 31 maxx(); 32 return 0; 33 }