单调栈

什么是单调栈

单调栈是一种数据结构，可以帮助我们在 $O(n)$ 的时间复杂度内找出 $a_i$ 左/右第一个大于(等于)/小于(等于) $a_i$ 的数。

那具体是如何实现的呢

通过实现一个栈存储待填答案的元素，当遍历到一个元素时：

(1) 将栈中所有找到答案的值弹出，记录答案；

(2) 然后当前元素成为待填答案的元素，压入栈。

• 我们发现在上一次执行 (1) 的时候顺便维护了栈的单调性，所以在当前步骤 (1) 时直接弹出栈顶元素就可以找出所有 $a_i$ 可以贡献答案的值。 （听不懂没关系，看完例子就明白了）

以 洛谷P5788 为例子，我们要右边找一个数列中第 $i$ 个元素之后第一个大于 $a_i$ 的元素的下标。

• 首先创建一个栈，注意：这里stack里面存的是元素下标，当然你也可以用结构体，但是不推荐

stack<int> st;

• 然后遍历数组

for (int i = 1;i <= n;i++) {

}

• 当栈顶元素小于它时，栈顶元素就找到了答案，由于遍历的顺序性，所有元素必定都被第一个元素所更新。注意要判断栈非空否则会 Runtime Error

for (int i = 1;i <= n;i++) {
    while (!st.empty() && a[st.top()]<a[i]) f[st.top()] = i, st.pop();
}

• 最后，$a_i$ 成为了待更新的元素，压入栈

for (int i = 1;i <= n;i++) {
    while (!st.empty() && a[st.top()]<a[i]) f[st.top()] = i, st.pop();
    st.push(i);
}

过程演示：

$a = {1,4,2,3,5}$

$st = {}$

当前遍历 $i=1,a_i=1$ $st = {1}$ 当前遍历 $i=2,a_i=4$

$4 > a_1$ 所以 st.pop()，$f(1)=2$

$st = {2}$

当前遍历 $i=3,a_i=2$

$2 \le a_2$ 所以 st 不弹出

$st = {2,3}$

当前遍历 $i=4,a_i=3$

$3 > a_3$ 所以 st.pop()，$f(3)=4$

$st = {2,4}$

当前遍历 $i=5,a_i=5$

$5 > a_4$ 所以 st.pop()，$f(4)=5$

$st = {2}$

$5 > a_2$ 所以 st.pop()，$f(2)=5$

$st = {}$

最后 $5$ 入栈，后面没有比它更大的了，所以$f(5)=0$

完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e6+5;
int a[N], f[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    stack<int> st;
    for (int i = 1;i <= n;i++) {
        while (!st.empty() && a[st.top()]<a[i]) f[st.top()] = i, st.pop();
        st.push(i);
    }
    for (int i = 1;i <= n;i++)cout << f[i] << ' ';
}