滑动窗口

使用数据结构： 单调队列(实际是单调双端队列，队头队尾可删）

每次维护一个窗口，为了满足某种性质，需要对队列进行维护。

如何判断是否有单调性？
先看暴力是怎么做的，然后正常维护过程，然后把不需要的元素删掉，之后判断，剩余的元素是否具有单调性。

看下面的例子，题目的要求是找窗口中的最小值。

对于这样的一个数组，窗口大小为3，随着i的不断增加，寻找窗口内的最小值，我们可以发现只要 -1 存在一天，前面的 1 和 3就不会被输出。

同样：

只要-1存在，比它大的就不会被用到。
...

所以这个队列里面的元素就是单调减小的。

例题：
154. 滑动窗口

参考代码：

#include<iostream>
using namespace std;

const int N = 1e6+10;
int a[N],q[N];
int hh = 0, tt = -1;
int n,k;

int main(){
    cin>>n>>k;
    for(int i = 0; i < n; i++) cin>>a[i];
    
    for(int i = 0; i < n; i++){
        //如果队头滑出了队列 更新队头
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        //如果队尾的元素大于等于当前元素，则一直不会被用到
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        
        if(i >= k - 1) cout<<a[q[hh]]<<" ";
    }
    puts("");
    
    hh = 0,tt = - 1;
    
    for(int i = 0; i < n; i++){
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if(i >= k - 1) cout<<a[q[hh]]<<" ";
    }
    
    
    return 0;
}