题解 | #滑动窗口#

单调队列维护每个区间中有可能能成为最值的数即可

队列存元素下标（否则不知道怎么判断队内元素已经超出窗口了）

#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e6+5;
int n,k;
int a[Nmax];
deque<int> max_dq,min_dq;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n>>k;
    
    for(int i = 1;i <= n;i++)
        cin>>a[i];

    for(int i = 1;i <= n;i++){    //求最小值
        if(!min_dq.empty())
            if(min_dq.size() == k || i - min_dq.back() >= k)
                min_dq.pop_back();
        while(!min_dq.empty() && a[min_dq.front()] > a[i]) min_dq.pop_front();
        min_dq.push_front(i);
        if(i >= k) cout<<a[min_dq.back()]<<' ';
    }
    cout<<'\n';
    for(int i = 1;i <= n;i++){    //求最大值
        if(!max_dq.empty())
            if(max_dq.size() == k || i - max_dq.back() >= k)
                max_dq.pop_back();
        while(!max_dq.empty() && a[max_dq.front()] < a[i]) max_dq.pop_front();
        max_dq.push_front(i);
        if(i >= k) cout<<a[max_dq.back()]<<' ';
    }
    return 0;
}