【题目大意】

在一个长度为$n$的橱窗里，有一个长度为$k$的窗口可以左右滑动，求出窗口从左滑到右每次的最大值和最小值。

【思路分析】

单调队列的特点就是可以从队头出队也可以从队尾出队，这里以单调递减为例讲解一下。

$q$是队列，$p$记录队列中的元素原本的编号。

现在元素$a_i$要入队，那么我们将其与队尾元素比较$$while(head<=tail且q[tail]<=a[i])tail--$$循环跑一下，然后把这个元素插入队尾$q[++tail]=a[i]$，同时记录编号$p[tail]=i$。注意题目限制了窗口长度，所以要把在窗口之外的队内元素从队头去掉$$while(i-p[head]>k)head--$$此时由于队列的单调性，队首元素即为所求的最大值。

【代码实现】

 

1 #include
      
        2 #define rg register 3 #define go(i,a,b) for(rg int i=a;i<=b;i++) 4 using namespace std; 5 const int N=1e6+2; 6 int n,k,a[N]; 7 int p[N],q[N],head,tail; 8 int main(){ 9     scanf("%d%d",&n,&k);10     go(i,1,n) scanf("%d",&a[i]);11     head=1;tail=0;12     go(i,1,n){13         while(head<=tail&&q[tail]>=a[i]) tail--;14         q[++tail]=a[i];15         p[tail]=i;16         while(p[head]<=i-k) head++;17         if(i>=k) printf("%d ",q[head]);18     }19     puts("");head=1;tail=0;20     go(i,1,n){21         while(head<=tail&&q[tail]<=a[i]) tail--;22         q[++tail]=a[i];23         p[tail]=i;24         while(p[head]<=i-k) head++;25         if(i>=k) printf("%d ",q[head]);26     }27     return 0;28 }