滑动窗口

题意：略。

题记：
取区间最大值的情况：取维护一个双端队列，每当a[i]进入队尾时，在a[i]之前进入队列且比a[i]小的数是不可能成为区间最大值了，所以这些数可以在队列中删掉。取最小值同理。

#include<bits/stdc++.h>

using namespace std;
const int N=1e6+10;
int a[N];
deque<int>q;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        while(!q.empty()&&i-q.front()+1>k) q.pop_front();
        while(!q.empty()&&a[q.back()]>a[i]) q.pop_back();
        q.push_back(i);
        if(i>=k&&i!=n)cout<<a[q.front()]<<' ';
        else if(i==n)cout<<a[q.front()]<<endl;
    }
    q.clear();
    for(int i=1;i<=n;i++){
        while(!q.empty()&&i-q.front()+1>k) q.pop_front();
        while(!q.empty()&&a[q.back()]<a[i]) q.pop_back();
        q.push_back(i);
        if(i>=k&&i!=n)cout<<a[q.front()]<<' ';
        else if(i==n)cout<<a[q.front()]<<endl;
    }
    return 0;
}