洛谷P1886--滑动窗口(单调队列模板)

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> a;
vector<int> q;
int n,k;
void findMin(){
    int head=1,tail=0;
    for(int i=1;i<=n;i++){
        while(head<=tail&&q[head]+k<=i)
            head++;
        while(head<=tail&&a[q[tail]]>a[i])
            tail--;
        q[++tail]=i;
        if(i>=k)
            cout<<a[q[head]]<<‘ ‘;
    }
    cout<<endl;
}
void findMax(){
    int head=1,tail=0;
    for(int i=1;i<=n;i++){
        while(head<=tail&&q[head]+k<=i)
            head++;
        while(head<=tail&&a[q[tail]]<a[i])
            tail--;
        q[++tail]=i;
        if(i>=k)
            cout<<a[q[head]]<<‘ ‘;
    }
    cout<<endl;
}
int main(){
    cin>>n>>k;
    a.resize(n+1);
    q.resize(n+1);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    findMin();
    findMax();
    return 0;
}