单调队列

#include<bits/stdc++.h>
using namespace std;
struct st{
    int num,val;    
}a[1000005];
deque<st>q; //最小值
deque<st>p; //最大值
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i].val;
        a[i].num=i;
    }
//    q.push_back(a[1]);
//    p.push_back(a[1]);
    for(int i=1;i<=n;i++){
                while(!q.empty()&&q.back().val>=a[i].val){
                    q.pop_back();
                }
                q.push_back(a[i]);
            while(i-k>=q.front().num)q.pop_front();
        if(i>=k)
        cout<<q.front().val<<" "; 
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
                while(!p.empty()&&p.back().val<=a[i].val){
                    p.pop_back();
                }
                p.push_back(a[i]);
            while(i-k>=p.front().num)p.pop_front();
        if(i>=k)
        cout<<p.front().val<<" "; 
    }
}

链接https://www.luogu.com.cn/problem/P1886