【模板】单调栈

本题是一道单调栈的模板题。

首先说说什么是单调栈。

何为单调栈？顾名思义，单调栈即满足单调性的栈结构。——OI-Wiki

~~那什么是单调呢？~~

当函数 f(x) 的自变量在其定义区间内增大（或减小）时，函数值f(x)也随着增大（或减小），则称该函数为在该区间上具有单调性。——百度百科

其实很简单，只要序列 $r$ 满足以下条件，就可以被称为单调的：

$\forall i,0<i<|r|,r_i<r_{i+1}$ （单调递增）
$\forall i,0<i<|r|,r_i\le r_{i+1}$ （单调不严格递增）
$\forall i,0<i<|r|,r_i>r_{i+1}$ （单调递减）
$\forall i,0<i<|r|,r_i\ge r_{i+1}$ （单调不严格递减）

~~那什么是栈呢？~~

堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。——百度百科

现在把术语解释清楚了，下面我们就来康康单调栈有什么用。

一般来说，单调栈用来 $O(n)$ 时间复杂度查找序列上每个元素左/右边第一个大于/小于/大于等于/小于等于它的元素。

在知道单调栈之前，我们写这样的程序是这样写的（以右边大于为例）：

#include <bits/extc++.h>
#define int long long
using namespace std;
using namespace __gnu_pbds;
int r[65536], n;
signed main()
{
    scanf("%lld", &n);
    for (int i{1}; i <= n; i++)
        scanf("%lld", r + i);
    for (int i{1}; i <= n; i++)
    {
        bool f{};
        for (int j{i + 1}; j <= n; j++)
            if (r[j] > r[i])
            {
                printf("%lld ", j);
                f = true;
                break;
            }
        if (!f)
            printf("0 ");
    }
    return 0;
}

通过分析，我们可以得知，这段代码的时间复杂度为 $O(n^2)$ （双重循环），显然会TLE，所以很多年以后，珂学家们发现单调栈可以对这段代码进行优化，我现在就拿1 1 4 5 1 4 1 9 1 9 8 1 0作为 $r$ 数组的值告诉大家如何用单调栈解决这个问题。

栈内没有元素， $r_1$ 进栈；
栈顶元素不小于 $r_2$ ， $r_2$ 进栈；
栈顶元素小于 $r_3$ ， $r_3$ 把栈顶元素挤出去，并成为它的答案；
栈顶元素还是小于 $r_3$ ， $r_3$ 把栈顶元素挤出去，并成为它的答案；
栈内没有元素， $r_3$ 进栈；
栈顶元素小于 $r_4$ ， $r_4$ 把栈顶元素挤出去，并成为它的答案；
栈内没有元素， $r_4$ 进栈；
栈顶元素不小于 $r_5$ ， $r_5$ 进栈；
栈顶元素小于 $r_6$ ， $r_6$ 把栈顶元素挤出去，并成为它的答案；
栈顶元素不小于 $r_6$ ， $r_6$ 进栈；
栈顶元素不小于 $r_7$ ， $r_7$ 进栈；
栈顶元素小于 $r_8$ ， $r_8$ 把栈顶元素挤出去，并成为它的答案；
栈顶元素还是小于 $r_8$ ， $r_8$ 把栈顶元素挤出去，并成为它的答案；
栈顶元素还是小于 $r_8$ ， $r_8$ 把栈顶元素挤出去，并成为它的答案；
栈内没有元素， $r_8$ 进栈；
栈顶元素不小于 $r_9$ ， $r_9$ 进栈；
栈顶元素小于 $r_{10}$ ， $r_{10}$ 把栈顶元素挤出去，并成为它的答案；
栈顶元素不小于 $r_{10}$ ， $r_{10}$ 进栈；
栈顶元素不小于 $r_{11}$ ， $r_{11}$ 进栈；
栈顶元素不小于 $r_{12}$ ， $r_{12}$ 进栈；
栈顶元素不小于 $r_{13}$ ， $r_{13}$ 进栈；

最后，栈内还剩下 $r_8$ 、 $r_{10}$ 、 $r_{11}$ 、 $r_{12}$ 、 $r_{13}$ ，它们没有答案。

至此，我们用 $O(n)$ 的时间复杂度算出来了序列上每个元素右边第一个大于它的元素。左边、小于/大于等于/小于等于同理。这就是单调栈的用法。

最后，贴上交流电(AC)代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int r[3000006],n,ans[3000006];
stack<int>s;
signed main()
{
    cin>>n;
    for(int i {1}; i<=n; i++)
        cin>>r[i];
    for(int i {1}; i<=n; i++)
    {
        while(!s.empty()&&r[s.top()]<r[i])
            ans[s.top()]=i,s.pop();
        s.push(i);
    }
    for(int i {1}; i<=n; i++)
        cout<<ans[i]<<' ';
    return 0;
}

谢谢大家的观看！