解法1：堆

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

const int N=1e6+5;
int a[N];
int n, k;
vector<int> minRes;
vector<int> maxRes;

// 使用最小堆求解(要求堆支持删除操作)
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    memset(a, 0x00, sizeof a);

    cin>>n>>k;
    multiset<int, less<int>> minHeap;

    for(int i=0; i<n; ++i){
        cin>>a[i];
        minHeap.insert(a[i]);
        if(i>=k){
            minHeap.erase(minHeap.find(a[i-k]));
        }
        if(i>=k-1){
            minRes.push_back(*minHeap.begin());
            maxRes.push_back(*prev(minHeap.end()));
        }

    }

    for(auto &e: minRes) cout<<e<<" ";
    cout<<endl;
    for(auto &e: maxRes) cout<<e<<" ";

    return 0;
}

解法2：单调队列

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

const int N=1e6+5;
int a[N]; // 原始数组
int b[N]; // 单调队列
int n, k;

int main(){
    // 滑动窗口&单调队列
    memset(a, 0x00, sizeof a);
    memset(b, 0x00, sizeof b);
    cin>>n>>k;
    for(int i=0; i<n; ++i) cin>>a[i];
    int HEAD=0;
    int TAIL=-1;

    // 单调队列存储窗口中的最小值
    for(int i=0; i<n; ++i){
        // 判断队首是否滑出窗口
        if(HEAD<=TAIL && i-k+1>b[HEAD]) ++HEAD;
        while(HEAD<=TAIL && a[b[TAIL]]>=a[i]) --TAIL;
        b[++TAIL]=i;
        if(i>=k-1) cout<<a[b[HEAD]]<<" ";
    }
    cout<<endl;

    // 单调队列存储窗口中的最大值
    HEAD=0, TAIL=-1;
    for(int i=0; i<n; ++i){
        if(HEAD<=TAIL && i-k+1>b[HEAD]) ++HEAD;
        while(HEAD<=TAIL && a[b[TAIL]]<=a[i]) --TAIL;
        b[++TAIL]=i;
        if(i>=k-1) cout<<a[b[HEAD]]<<" ";
    }
    cout<<endl;


    return 0;
}