154. 滑动窗口

思路：

窗口用队列来存储，类似于单调栈，只不过不是从右往左删除，而是从左往右删除，每次将窗口内比自己大的或者相等的数从左边弹出，因为窗口往右移动的过程中，最小值不可能选取比当前值还有小的数。
例如：窗口[1,3,-1]中应该将1、3弹出

AC代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10;

int n,k;
int a[N],q[N],head,tail;//队列里面存储下标
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    //先算窗口最小值
    head=0,tail=-1;
    for(int i=0;i<n;i++){
        if(i-q[head]+1>k&&head<=tail) head++;//非空队列且队列长度大于窗口长度，窗口向右移动一格
        while(a[q[tail]]>=a[i]&&head<=tail) tail--;//将窗口内比当前大的值都删除掉
        q[++tail]=i;
        if(i>=k-1) printf("%d ",a[q[head]]);
    }
    printf("\n");
    
    //再算窗口最大值
    head=0,tail=-1;
    for(int i=0;i<n;i++){
        if(i-q[head]+1>k&&head<=tail) head++;//非空且队列长度大于窗口长度，窗口向右移动一格
        while(a[q[tail]]<=a[i]&&head<=tail) tail--;//将窗口中比当前小的都删掉
        q[++tail]=i;
        if(i>=k-1) printf("%d ",a[q[head]]);
    }
    printf("\n");
}