【每日一题】3月30日，滑动窗口（单调队列）

单调队列，就是一种单调的队列，队列里的元素都是单调的。
单调队列如何维护队列的单调性，通过两个指针,head和tail.
注意的是单调队列中存的是元素的下标,所以我们才能来判断队首是不是在该区间内.
通过head <= tail来判断是否队空.
如果队首元素已经不在区间内,就移动head指针.
每次从队尾开始比较,不符合的从出队,移动tail指针,并且将当前元素插入.

AC Code:
#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<math.h>
#include<stack>
#include<map>
#include<limits.h>
#include<vector>
#include<string.h>
#include<string>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e6+5;
const LL M = 2000000011;
#define pi acos(-1)
#define INF 1e8
#define INM INT_MIN
#define pb(a)  push_back(a)
#define mk(a,b) make_pair(a,b)
#define dbg(x) cout << "now this num is " << x << endl;
#define met0(axx) memset(axx,0,sizeof(axx));
#define metf(axx) memset(axx,-1,sizeof(axx));
#define sd(ax) scanf("%d",&ax)
#define sld(ax) scanf("%lld",&ax)
#define sldd(ax,bx) scanf("%lld %lld",&ax,&bx)
#define sdd(ax,bx) scanf("%d %d",&ax,&bx)
#define sddd(ax,bx,cx) scanf("%d %d %d",&ax,&bx,&cx)
#define sfd(ax) scanf("%lf",&ax)
#define sfdd(ax,bx) scanf("%lf %lf",&ax,&bx)
#define pr(a) printf("%d\n",a)
#define plr(a) printf("%lld\n",a)
int a[N],que[N];
int main()
{
    int n,k;sdd(n,k);
    for(int i=1;i<=n;++i) sd(a[i]);
    int head = 1,tail = 0,f = 0;
    for(int i=1;i<=n;++i)
    {
        while(head <= tail && que[head]+k <= i) head++;
        while(head <= tail && a[que[tail]] > a[i]) tail--;
        que[++tail] = i;//入队
        if(i >= k)
        {
            if(f) printf(" %d",a[que[head]]);
            else printf("%d",a[que[head]]);
            f = 1;
        }
    }
    printf("\n");
    head = 1,tail = 0,f = 0;
    for(int i=1;i<=n;++i)
    {
        while(head <= tail && que[head]+k <= i) head++;
        while(head <= tail && a[que[tail]] < a[i]) tail--;
        que[++tail] = i;
        if(i >= k)
        {
            if(f) printf(" %d",a[que[head]]);
            else printf("%d",a[que[head]]);
            f = 1;
        }
    }
    printf("\n");
    //system("pause");
    return 0;
}