单调栈解决一类问题：给定一个数组 arr，求每个元素左边第一个比它小的元素的下标。输出一个 L 数组，L[i] 表示 arr 中第 i 个数左边比它小的元素的下标。

原题链接

伪代码：

1
2
3
4
5
6
7
8
9
枚举下标 [1, n)
    // 只要栈顶元素比当前枚举的大，就出栈
    while arr[stk.top()]>=arr[i] stk.pop()
    // 如果全部出栈了，说明i左边没有比它小的
    if stk.empty() L[i]=-1;
    // 否则i左边第一个比它小的就是栈顶
    else L[i]=stk.top();
    // 当前下标入栈
    stk.push(i)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
const int N = 1e5+10;
int stk[N], tt;

int main() {
    int n;
    cin >> n;
    for(int i=0;i<n;i++) {
        int x;
        cin >> x;
        // 栈不空，且栈顶元素比当前元素大就弹出
        while(tt && stk[tt] >=x) tt--;
        // 出栈操作完毕后，栈顶元素就是左边第一个比当前元素小的
        if(tt) cout << stk[tt] << ' ';
        // 如果全部出栈了，那么左边就没有比当前元素小的，输出 -1
        else cout << -1 << ' ';
        // 最后将当前元素压入栈中
        stk[++tt] = x;
    }
    return 0;
}