单调队列

一种需要 人工 根据一定条件, 来筛除一些队列中已经没有资格再混下去的元素的数据结构

张三原本在学校的 OI 队伍, 但天天不思进取, 上课只会打小游戏, 结果......
身为高二学长的他竟然连高一新晋的 OIer 都比不过, 于是他们学校的 yxf 老师就将他开除了队伍, 因为 新晋OIer年纪比他小, 能力比他强, 张三的整体价值已经比不过新晋OIer了 QwQ

蒟蒻代码

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

const int N=1e6+5;
int n,k;
int q[N];   // 存储元素索引, 方便判断出队
int head,tail;
int a[N];

void monotoneMin(){
    // memset(q,0,sizeof(q));
    head=1, tail=0;
    for(re int i=1;i<=n;i++){
        while(head<=tail && a[q[tail]]>=a[i]) tail--;
        q[++tail]=i;
        while(head<=tail && q[head]+k<=i) head++;
        if(i>=k) cout<<a[q[head]]<<" ";
    }
    cout<<endl;
}

void monotoneMax(){
    // memset(q,0,sizeof(q));
    head=1, tail=0;
    for(re int i=1;i<=n;i++){
        while(head<=tail && a[q[tail]]<=a[i]) tail--;
        q[++tail]=i;
        while(head<=tail && q[head]+k<=i) head++;
        if(i>=k) cout<<a[q[head]]<<" ";
    }
    cout<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
#endif
    // ======================================================================
    cin>>n>>k;
    for(re int i=1;i<=n;i++) cin>>a[i];
    monotoneMin();
    monotoneMax();
    // ======================================================================
end:
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;
}