AcWing 154.滑动窗口

原题链接如下：
154. 滑动窗口 - AcWing题库

在直播课里，y总给我们讲了一个很重要的思想，对于这种类型的问题，我们一般都是先去找一个常规的暴力做法，然后我们从暴力做法里去发现，有哪些东西是可以删去，也即可以优化的，就比如在这两道单调栈和队列的题目里面，我们是要找符合条件的数字，我们在暴力法进行模拟的每一步的时候，我们应该多去想一想，有些数字是不是永远可能不会作为答案输出，我们需要抓住某些性质，来对我们的解法进行优化，求各种最大最小，我们都可以采用这种思想，于是我们这两道题就有了单调xx的解法，当我们在遍历的过程中，不断地去找更大的更小的，比当前条件更差的我们就把他们除去，因此就会形成单调的，最后特别方便我们来找最大或者最小

#include<iostream>
using namespace std;
const int N = 1000010;
//注意:q[N]中存放是对应a[N]数组的下标
int a[N],q[N];

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i = 0;i<n;i++)scanf("%d",&a[i]);
    
    //hh和tt可以看成我们队列的头尾指针
    int hh = 0,tt = -1;
    for(int i = 0;i<n;i++)
    {
        //滑动窗口左端移动 维持滑动窗口的大小固定为k
        if(hh<=tt&&i-k+1>q[hh])hh++;
        //如果队尾的数字比当前的更大，说明队尾这个数字不行了 肯定不是最小值 所以将他除去
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
        q[++tt] = i;
        //滑动窗口大小开始大于3之后，每次移动就输出一次
        if(i>=k-1)printf("%d ",a[q[hh]]);
    }
    cout<<endl;
    //puts("");
    //求最大值也和上面一样 换个不等号而已
    hh = 0,tt = -1;
    for(int i=0;i<n;i++)
    {
        if(hh<=tt&&i-k+1>q[hh])hh++;
        while(hh<=tt&&a[q[tt]]<=a[i])tt--;
        q[++tt] = i;
        if(i>=k-1)printf("%d ",a[q[hh]]);
    }
    return 0;
}