单调队列模板

Seshen / 2023-08-14 / 原文

好的，这是一个晴朗的夜晚。

- 苯荏水平不高甚至菜亖，博客仅仅写给自己避免自己忘记学了什么，也仅据我理解写出，不严谨，非常不严谨。

单调队列。

在原序列基础上，维护一个单调的序列。

单调队列中的元素在原序列中的相对位置不变，且在单调队列中的元素是单调的。

基本模板题：https://www.luogu.com.cn/problem/P1886

代码：

//Luogu P1886滑动窗口模板/单调队列
//心有志向，则无畏阻挡
#include <bits/stdc++.h>
using namespace std;
int n, k;
const int N = 1e6 + 5;
struct stu {
    int id, num;//表示元素在原序列中的序号与对应的值
};
stu now, a[N];
deque<stu>dmax, dmin;//维护两个单调队列，分别维护区间最大值与区间最小值
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i].num);
        a[i].id = i;
    }//read
    for (int i = 1; i <= n; i++) {//求区间最小值
        now = a[i];
        while (!dmin.empty() && dmin.back().num >= now.num) {
            //若之前的右端数字大于当前数字，则右端数字不可能为当前区间最小值
            //维护一个单调递增序列
            dmin.pop_back();
        }
        while (!dmin.empty() && dmin.front().id <= i - k) {//窗格内的数量超过k了。数量为i-k+1，减去当前元素则是i-k
            dmin.pop_front();
        }
        dmin.push_back(now);//放入当前元素
        if (i >= k) {
            printf("%d ", dmin.front().num);
        }//如果窗格长度>k
    }//min
    puts(" ");
    for (int i = 1; i <= n; i++) {
        now = a[i];
        while (!dmax.empty() && dmax.back().num <= now.num) {
            dmax.pop_back();
        }
        while (!dmax.empty() && dmax.front().id <= i - k) {
            dmax.pop_front();
        }
        dmax.push_back(now);
        if (i >= k) {
            printf("%d ", dmax.front().num);
        }
    }//max
    return 0;
}