单调队列从入门到精通(

单调队列,即单调递减或单调递增的队列。使用频率不高,但在有些程序中会有非同寻常的作用。

百度百科

在日常的学习中,我们有时会遇到一些非常典型的题目:

在一个给定的长度为n的区间中,要求你对每一个i∈[1,n-m]输出区间[i,m+i]中的最大值

不难想到可以使用O(nm)的时间复杂度的算法来解决这个问题。

也有同学会想到利用线段树或者树状数组维护区间最值,这样时间复杂度就降为O(nlogn)

也有同学说这道题可以利用RMQ算法O(nlogn)预处理,O(1)求出。

但是实际上这个问题可以使用单调队列来达到O(n)的时间复杂度。

单调队列本质就是一个元素单调增或减的队列,核心代码并不长,但是对于不同的题目,相对应的代码也不尽相同,这里以POJ2823来举例: https://acm.njupt.edu.cn/problem/POJ2823

#include <cstdio>
#include <cstring>
using namespace std;
#define N 1000010
struct Node {
    int index;
    int value;
} max_q[N * 2], min_q[N * 2];
int max_res[N], min_res[N];
int front_max, front_min;
int back_max, back_min;
int n, k, c;
int main() {
    scanf("%d%d", &n, &k);
    scanf("%d", &c);
    max_q[back_max].value = c;
    min_q[back_min].value = c;
    max_q[back_max].index = 0;
    min_q[back_min].index = 0;
    for (int j = 1; j < k; j++) {
        scanf("%d", &c);

        while (back_max >= 0 && max_q[back_max].value <= c) back_max--;
        max_q[++back_max].value = c;
        max_q[back_max].index = j;

        while (back_min >= 0 && min_q[back_min].value >= c) back_min--;
        min_q[++back_min].value = c;
        min_q[back_min].index = j;
    }
    max_res[0] = max_q[0].value;
    min_res[0] = min_q[0].value;
    for (int j = k; j < n; j++) {
        scanf("%d", &c);

        if (max_q[front_max].index == j - k) front_max++;
        while (back_max >= front_max && max_q[back_max].value <= c) back_max--;
        max_q[++back_max].value = c;
        max_q[back_max].index = j;
        max_res[j - k + 1] = max_q[front_max].value;

        if (min_q[front_min].index == j - k) front_min++;
        while (back_min >= front_min && min_q[back_min].value >= c) back_min--;
        min_q[++back_min].value = c;
        min_q[back_min].index = j;
        min_res[j - k + 1] = min_q[front_min].value;
    }
    for (int j = 0; j < n - k + 1; j++) printf("%d ", min_res[j]);
    printf("\n");
    for (int j = 0; j < n - k + 1; j++) printf("%d ", max_res[j]);
    printf("\n");
    return 0;
}

而虽然对于不同类型的题目有不一样的代码,我们还是可以从中找到一些规律。

一般来说单调队列的流程一般为:

1.将前m个数取出,放入队列中

2.将剩余数依次加入到队列中,每次加入之前先踢出队尾不合要求的元素,然后更新答案,然后再踢出队头不合要求的数,最后再将要加入的元素插入队头。

单调队列在部分题目中非常关键,同时他也应用于具有决策单调性的DP中,即斜率优化DP。

发表评论

电子邮件地址不会被公开。 必填项已用*标注