【数据结构】单调队列与单调栈

更新于 分类于 ， 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

单调队列和单调栈利用队列和栈两个基本的数据结构维护一个单调序列，用来解决具有单调性的问题

单调队列

  • 维护一个队列，使得队列里的元素具有单调性

  • 很好想，看新来的元素是否能插入队尾（即插入后是否还符合单调性质），若不行就弹出队尾元素并继续上述判断，直到可以插入队尾

  • 滑动窗口：设定这个队列维护的长度不超过kk （窗口长度）

    • 每次插入了元素之后，检查队首元素是否还在窗口范围内，不在则出队

    • 特别注意，这里不是队列的长度而是队列中元素在原来线性数组中的元素距离。由元素入队的顺序可知，只要检查队首与队尾元素的距离即可

  • 应用：任意固定长度区间的最值，时间复杂度O(N)O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//以单调最小值为例
int head = 1, tail = 0; //当head>=tail时队不空
for (int i = 1; i <= n; i++)
{
    while (head <= tail && q[tail] >= a[i])
        tail--;
    //如果队尾元素比a[i]大，那么队尾元素有生之年都不可能成为最小值,出队
    //队列长度由后面操作控制，不需担心超过窗口范围
    q[++tail] = a[i]; //a[i]入队
    p[tail] = i;      //记录队尾元素的坐标
    while (p[head] <= i - k)
        head++; //如果队首已经不在窗口范围内，出队
    if (i >= k)
        printf("%d ", q[head]);
}

//单调最大值
head = 1, tail = 0;
for (int i = 1; i <= n; i++)
{
    while (head <= tail && q[tail] <= a[i])
        tail--;
    q[++tail] = a[i];
    p[tail] = i;
    while (p[head] <= i - k)
        head++;
    if (i >= k)
        printf("%d ", q[head]);
}

单调栈

  • 维护一个具有单调性的栈，原理与单调队列基本相同

  • 应用：找向右/左沿伸一直小的位置（换种说法，某个元素作为最值的区间范围）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (int i = 1; i <= n; i++)
{
    while (top > 0 && a[stk[top]] < a[i])
        top--;    // 维护一个单调递减的栈
    pos[i][0] = stk[top] + 1; // i左边一直比a[i]小的最远延伸位置
    stk[++top] = i;
}
top = 0;
for (int i = n; i > 0; i--)
{
    while (top > 0 && a[stk[top]] > a[i])
        top--;
    pos[i][1] = top ? stk[top] - 1 : n; // i右边一直比a[i]大的最远延伸位置
    stk[++top] = i;
}

题目

解决题目的关键是找单调的特征，然后应用以上两种数据结构。两种结构有时候都可以用，有时不行，要具体分析题目中的单调性质。

单调队列

POJ2823/P3865 模板

洛谷P2251 滑动窗口

单调栈

Uva1619 单调队列写的，求最小值覆盖区间

洛谷P4697

洛谷P6801

洛谷P5923 没看懂。。。