单调栈与优先队列

单调栈

即栈内的元素是有某种单调性的。

用于求特定问题的解。

作用情景

[求一个数列的每个数的左边第一个比它小的数字](830. 单调栈 - AcWing题库)

要求左边第一个比它小的数，那么在之前每一个数入栈的时候就进行判断，只将满足递减单调性的数据存入，其余的弹出

#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        //如果栈是非空的，且栈顶元素不比要入栈的元素小，将栈顶弹出，以形成单调栈
        while (tt && stk[tt] >= x)
            tt--;
        //形成单调栈以后的栈顶就是要找的第一个比要入栈元素小的值
        if (tt)
            printf("%d ", stk[tt]);
        else
            printf("-1 ");
        //最后将这个元素入栈
        stk[++tt] = x;
    }
    return 0;
}

优先队列

与单调栈的定义类似，优先队列里的元素是按照某种单调性排列的。

使用优先队列可以简化特定要求的与队列有关的问题。

作用情景

[滑动窗口](154. 滑动窗口 - AcWing题库)

一组数据

给定一个大小为 k的窗口，从数组的头开始滑动，窗口里最多只能同时存在k个数。

求每次滑动时，窗口里的最大值和最小值。

与优先队列的处理方式类似，只将满足单调性的元素从队尾入队，不满足的 从队尾出队

#include <iostream>

using namespace std;

const int N = 1000010;

int n, k;
//a[N]数组中存储要处理的数组，q[N]数组中存储队列里的数在a[N]数组里的下标
int a[N], q[N];

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    //定义队头和队尾
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++)
    {
        //使用 i - k + 1 来控制队列（滑动窗口）中的元素数量，每当队列中的元素超出k， 就把队头元素出队
        if (hh <= tt && q[tt] - k + 1 > q[hh])
            hh++;
        //要入队的元素要比队列中的所有元素都要大
        while (hh <= tt && a[q[tt]] >= a[i])
            tt--;
        q[++tt] = i;
        if (i >= k - 1)
            //队头的元素永远是最小的
            printf("%d ", a[q[hh]]);
    }
    printf("\n");
    //找最大值与最小值方法一样，改变入队的限制即可
    hh = 0, tt = -1;
    for (int i = 0; i < n; i++)
    {
        if (hh <= tt && i - k + 1 > q[hh])
            hh++;
        //要入队的元素要比队列中的所有元素都小
        while (hh <= tt && a[q[tt]] <= a[i])
            tt--;
        q[++tt] = i;
        if (i >= k - 1)
            printf("%d ", a[q[hh]]); //输出队头的最大元素
    }
    return 0;
}

总结

单调栈和优先队列的使用是为了满足特定集中情况下的算法需求，应用的场景比较有限

通常的使用场景是：

某个问题使用到了栈和队列的结构，但是朴素算法的遍历的复杂度太高，单调栈和优先队列可以优化栈和队列，使其具有一定的单调性，降低解决这些问题的复杂度。