C++代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e6 + 5;
int a[N], q[N];
int head, tail;
int n, k;
int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    head = -1;
    tail = -1;
    //遍历结束，队内元素单调
    for(int i = 0; i < n; i ++)
    {
        if(i - q[head + 1] == k) head ++;//滑动该窗口
        while((head < tail) && a[i] <= a[q[tail]]) {//队不空&&当前元素比队尾小，则队尾元素永远也不可能再用到
            tail --;//从队尾出队
        }
         q[++ tail] = i;//入队
        if(i >= k - 1) cout << a[q[head + 1]] << " ";
    }
    cout << endl;
    head = -1;
    tail = -1;
    for(int i = 0; i < n; i ++)
    {
        if(i - q[head + 1] == k) head ++;
        while((head < tail) && a[i] >= a[q[tail]]) {
            tail --;
        }
        ++tail; q[tail] = i;
        if(i >= k - 1) cout << a[q[head + 1]] << " ";
    }
    cout << endl;
    return 0;
}