单调栈

单调栈，顾名思义，就是把元素按照严格单调的顺序存在栈中（从「栈顶」到「栈底」）

可以加速查找数组中满足特定条件的数的过程，例如：

• 寻找左侧第一个比当前元素大的元素
• 寻找左侧第一个比当前元素小的元素
• 寻找右侧第一个比当前元素大的元素
• 寻找右侧第一个比当前元素小的元素

可以有效的将嵌套搜索的 $O(n^2)$ 的时间复杂度优化到 $O(n)$

关于栈的实现，可以使用 $STL$ 中的 stack 库实现，也可以利用数组和栈顶指针进行模拟操作（速度略快）

这里举一道例题具体说明：题目如下

题目描述

给出项数为 $n$ 的整数数列 $a_{1 \dots n}$

定义函数 $f(i)$ 代表数列中第 $i$ 个元素之后第一个大于 $a_i$ 的元素的下标，即 $f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}$。若不存在，则 $f(i)=0$

试求出 $f(1\dots n)$。

输入格式

第一行一个正整数 $n$

第二行 $n$ 个正整数 $a_{1\dots n}$

输出格式

一行 $n$ 个整数表示 $f(1), f(2), \dots, f(n)$ 的值

样例输入

5
1 4 2 3 5

样例输出

2 5 4 5 0

数据规模与约定

对于 $30\%$ 的数据，$n\leq 100$

对于 $60\%$ 的数据，$n\leq 5 \times 10^3$

对于 $100\%$ 的数据，$1 \le n\leq 3\times 10^6$，$1\leq a_i\leq 10^9$

首先介绍第一种方法——利用stack库实现：

题目要求查找 $a_i$ 之后的元素，所以我们需要先将所有数据存进数组，然后反向搭建单调栈

for (int i = 1; i <= n; i++) scanf("%d", &input[i]);//存入数组input

反向操作：

for (int i = n; i > 0; i--) {
    while (!stk.empty() && inp[stk.top()] <= inp[i]) stk.pop();
    ans[i] = stk.empty() ? 0 : stk.top();
    stk.push(i);
}

逐语句解释原理：

while (!stk.empty() && input[stk.top()] <= input[i]) stk.pop();

当 stk 栈不为空并且栈顶元素所存的下标值使得input[stk.top()] <= input[i]时

即当前选择的input[i]的值，大于等于input[stk.top()] 的值时，弹出栈顶元素

stk.push(i);

搭配赋值语句，将下标 i 存进栈中，这样我们就能保证栈中的元素是严格单调递增的

在退出 for 遍历前，还需要把查找到的目标元素的下标存进 ans 数组，便于输出答案

ans[i] = stk.empty() ? 0 : stk.top();

这里使用三元运算符，若 stk 栈为空，则把 ans[i] 赋值为 $0$ ，满足题意

若不为空，则将栈顶元素存储的下标值赋值给 ans[i]

完整代码如下：从下标为 $1$ 开始，符合题意

int inp[3000010], ans[3000010];
stack<int> stk;

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &inp[i]);
    for (int i = n; i > 0; i--) {
        while (!stk.empty() && inp[stk.top()] <= inp[i]) stk.pop();
        ans[i] = stk.empty() ? 0 : stk.top();
        stk.push(i);
    }
    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
    return 0;
}

接下来介绍模拟栈的实现：

首先定义一个数组空间模拟栈空间，以及一个指针模拟栈顶游标

int stk[3000010],tt;

和利用stack库的操作只有在实现单调栈的循环中有所不同：

for (int i = n; i > 0; i--) {
    while (tt && a[stk[tt]] <= a[i]) tt--;
    ans[i] = tt ? stk[tt] : 0;
    stk[++tt] = i;
}

同样的，首先判断模拟栈空间是否为空，以及当前元素是否大于等于栈顶元素所映射的元素值：

tt && a[stk[tt]] <= a[i]

循环到使栈内元素严格单调递增或空栈时退出

同理，可以写出由栈顶游标 tt 所实现的pop(),top(),empty(),push()操作

我们所定义的栈空间实际上是在stk[0]~stk[tt]的空间内，所以移动栈顶游标的位置，就是对栈顶元素进行操作

完整代码如下：

int a[3000010],stk[3000010],ans[3000010],tt;

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = n; i > 0; i--) {
        while (tt && a[stk[tt]] <= a[i]) tt--;
        ans[i] = tt ? stk[tt] : 0;
        stk[++tt] = i;
    }
    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
    return 0;
}

总结：

单调栈就是将无序的元素队列，选出其中的某些元素，构成一个元素值随元素下标的单调变化而单调变化的一个序列

优化实现 $O(n)$ 的查找时间复杂度