单调队列
题目链接

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

int n, k;
int a[N];
deque<int> q;

int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; ++ i) cin >> a[i];

    for(int i = 0; i < n; ++ i)
    {
        if(!q.empty() && q.back() - q.front() >= k - 1) 
            q.pop_front();
        while(q.size() && a[q.back()] >= a[i]) q.pop_back();
        q.push_back(i);        

        if(i - k + 1 >= 0) 
            cout << a[q.front()] << ' ';
    }

    cout << endl;
    q.clear();

    for(int i = 0; i < n; ++ i)
    {
        if(!q.empty() && q.back() - q.front() >= k - 1)
            q.pop_front();
        while(q.size() && a[q.back()] <= a[i]) q.pop_back();
        q.push_back(i);

        if(i - k + 1 >= 0)
            cout << a[q.front()] << ' ';
    }

    return 0;
}