单调队列

原理

见《进阶指南》第58页。

常记录元素的下标，而不是元素的数值。

在队头到队尾的方向上，有：

• 下标是单调递增的（队头最早入队，队尾最晚入队）。
• 下标对应的数值的单调的。

应用

求滑动窗口中的最值。

模板题

AcWing-154-滑动窗口

#include <iostream>
#include <queue>
using namespace std;

const int N = 1000010;
int n, k, a[N], res[N];
deque<int> dq;

void get_min_val () {
    for (int i = 1; i <= n; ++ i) {
        if (!dq.empty() && i - dq.front() + 1 > k) dq.pop_front();
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k) res[i] = dq.front();
    }
    for (int i = k; i <= n; ++ i)
        printf("%d ", a[res[i]]);
    printf("\n");
}
void get_max_val () {
    for (int i = 1; i <= n; ++ i) {
        if (!dq.empty() && i - dq.front() + 1 > k) dq.pop_front();
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k) res[i] = dq.front();
    }
    for (int i = k; i <= n; ++ i)
        printf("%d ", a[res[i]]);
    printf("\n");
}

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

    get_min_val();
    dq.clear();
    get_max_val();
    return 0;
}