题解 | Sliding Window

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main() {
    deque<int> dq;
    
    int n, k;
    cin >> n >> k;
    
    vector<int> a(n + 1);
    
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    for (int i = 1; i <= n; i++) {
        if (!dq.empty() && dq.front() + k == i) dq.pop_front();
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push_back(i);
        
        if (i >= k) cout << a[dq.front()] << ' ';
    }
    
    cout << '\n';
    
    dq.clear();
    
    for (int i = 1; i <= n; i++) {
        if (!dq.empty() && dq.front() + k == i) dq.pop_front();
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        
        if (i >= k) cout << a[dq.front()] << ' ';
    }
    
    return 0;
}