单调栈

题目链接：https://www.acwing.com/problem/content/832/

题目描述

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

输入描述

第一行包含整数 N，表示数列长度。
第二行包含 N 个整数，表示整数数列。

输出描述

共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。
1≤N≤105
1≤数列中元素≤109

示例

输入

5
3 4 2 7 5

输出

-1 3 -1 2 2

分析

首先，我们可以想到对每一个数从右往左扫描序列来找到离它最近的小于它的数字，时间复杂度为 $O(n^2)$ 。

单调栈，则是在暴力算法的基础上挖掘问题的性质来优化算法。

序列 $d$ 中的两个数，其下标分别为 $i$ 和 $j$ ，若下式同时成立：

$$\left\{\begin{array}{l} i<j \\ d_i>d_j \end{array}\right.$$

则对于任意下标大于 $j$ 的数，由于 $d_j$ 的存在，$d_i$ 必不可能是离它最近的小于它的数。

因此，对暴力算法的改良就呼之欲出了。我们维护一个栈，利用上面的性质删去一些没有必要存在的数字，从而加速算法。

显然，栈中的元素由栈底到栈顶单调递增，因此该数据结构称为单调栈。

每一个位置只会入栈一次（在枚举到它时），并且最多出栈一次。因此当我们从左向右/总右向左遍历数组时，对栈的操作的次数就为 $O(n)$ 。所以单调栈的总时间复杂度为 $O(n)$ 。

AC代码

---

#include <cstdio>

const int N = 1e5 + 10;
int n;
int stk[N], tt = 0;
//此处使用了数组模拟栈

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