思路

用一个（双端）单调队列来维护一个窗内的最小值序列，这样窗口每移动一格，当前窗内的最小值肯定是队头元素对应的值。事实上队列中的元素个数大部分时候应该是小于窗长k的。这里队列中存的是下标，我的理解应该是便于判断队头元素是否出队，否则需要用一个Pair来同时保存下标和值。

C 代码

#include <stdio.h>
#define N 1000010

int main() {
    int n, k, q[N], a[N], hh, tt = -1;

    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    for (int i = 0; i < n; i++) {
        // 窗每一次右移一格，最多有一个元素出队
        if (hh <= tt && i - k + 1 > q[hh]) hh++; 

        // 即使现在队尾元素a[q[tt]] 对应的值 跟a[i]相等，但是a[i]是在更后面的位置，在窗内待的时间也越长，所以一样要移除掉队尾元素
        while (hh <= tt && a[q[tt]] >= a[i]) tt--; 

        // 当前窗尾元素已经是i了,上一步是以a[i]的值去清除一些窗内无用值，这一步清除完之后，将下标i入队
        q[++tt] = i;
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }

    printf("\n");
    hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && i - k + 1 > q[hh]) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    return 0;
}