单调栈

贡献者： 有机物

　　 单调栈内部的元素都是单调递增或者递减的。单调栈处理问题的思想就是及时排除不可能的答案，从而可以更高效的求出答案。

　　 单调栈可以解决的问题很少，经典问题就是用 $O(n)$ 的时间复杂度处理这么一类问题：求出每个数左/右边第一个比它小/大的数。

　　 我们就用：求出每个数左边第一个比它小的数，如果没有输出 $-1$。这个问题来讲解。

　　 举个例子： 输入：3 4 2 7 9，输出：-1 3 -1 2 2。

　　 先想一下朴素算法怎么做： 两重循环来枚举，第一重循环枚举每个数 $a_i$，第二重循环从 $a_i$ 往左枚举每个数，直到找到第一个比 $a_i$ 小的数为止。

// 朴素算法的代码
cout << -1 << ' ';   // 第一个数的左边肯定没有比他小的数，所以先输出 -1
bool res = true;
for (int i = 0; i < n; i ++ ) {
    for (int j = i - 1; j >= 0; j -- )
        if (a[i] > a[j])
        {
            cout << a[j] << ' ';
            res = true;
            break;
        } else res = 0;
    
    if (!res) cout << -1 << ' ';
}

　　 上面的代码的时间复杂度显然是 $O(n^2)$ 的，我们来分析一下枚举的过程有没有什么性质，是不是有些元素是不是永远不会作为答案输出。 如果在枚举的过程中发现了这样一对数：$a_i \geqslant a_j, i < j$，那显然 $a_i$ 永远不会作为答案输出。因为 $a_j$ 比 $a_i$ 小，且比 $a_j$ 靠前，所以我们就可以用一个栈来维护 $a_i$ 左边的数，如果发现栈顶元素大于等于要插入的数 $x$，那么就可以把栈顶元素删了，我们就可以以一直删，直到发现了栈顶元素小于 $x$，那么栈顶元素就是答案，这样栈内的元素也就单调递减了。

// 单调栈代码
cin >> n;
while (n -- )
{
    int x;
    cin >> x;
    while (tt && stk[tt] >= x) tt -- ;  // 只要栈不为空且栈顶元素大于要插入的数 x，那么就删除栈顶元素
    if (!tt) printf("-1 ");             // 如果栈位空，则没有比该元素小的值
    else printf("%d ", stk[tt]);        // 栈顶元素就是左侧第一个比它小的元素
    stk[ ++ tt] = x;
}

// C++ STL

int n;
scanf("%d", &n);

stack<int> st;
while (n -- )
{
    int x;
    cin >> x;
    while (st.size() != 0 && st.top() >= x) st.pop();
    if (st.size() != 0) cout << st.top() << ' ';
    else cout << "-1" << ' ';
    st.push(x);
}

　　 图示