C++ 代码

/**
 * 利用两个单调栈，分别是存储最大值和最小值的数组“下标”。对于最小值的栈，栈中每个元素
 * 能保证它是附近几个元素中最小的一个。
 */

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)

int main() {
    int n, k;
    int a[N], _min[N], _max[N];
    int min_q[N], max_q[N], min_tt = -1, max_tt = -1;   // 最大和最小值两个栈及其栈顶指针
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", a + i);

    int l, t, r;
    for (int i = 0; i < n; i++) {   // 遍历数组所有元素
        r = i;
        while (min_tt > -1) {   // 栈不为空
            t = min_q[min_tt];
            if (a[t] <= a[r]) break;    // 只有新元素小于栈顶元素时，栈顶元素才出栈
            min_tt--;
            if (min_tt == -1) l = -1;
            else l = min_q[min_tt];
            for (int j = max(t - k + 1, l + 1); j <= min(r - k, t); j++)
                _min[j] = a[t]; // 涉及的滑动窗口最小值更新
        }
        min_q[++min_tt] = r;    // 将数组元素推入栈

        while (max_tt > -1) {
            t = max_q[max_tt];
            if (a[t] >= a[r]) break;
            max_tt--;
            if (max_tt == -1) l = -1;
            else l = max_q[max_tt];
            for (int j = max(t - k + 1, l + 1); j <= min(r - k, t); j++)
                _max[j] = a[t];
        }
        max_q[++max_tt] = r;
    }

    r = n;  // 队列中剩下所有的元素都能保证小（大）于在数组中后面的值
    while (min_tt > -1) {
        t = min_q[min_tt--];

        if (min_tt == -1) l = -1;
        else l = min_q[min_tt];

        for (int j = max(t - k + 1, l + 1); j <= min(r - k, t); j++)
            _min[j] = a[t];
    }

    while (max_tt > -1) {
        t = max_q[max_tt--];

        if (max_tt == -1) l = -1;
        else l = max_q[max_tt];

        for (int j = max(t - k + 1, l + 1); j <= min(r - k, t); j++)
            _max[j] = a[t];
    }

    for (int i = 0; i <= n - k; i++) printf("%d ", _min[i]);
    printf("\n");
    for (int i = 0; i <= n - k; i++) printf("%d ", _max[i]);

    return 0;
}