题目描述

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

输入样例

5
3 4 2 7 5

输出样例

-1 3 -1 2 2

单调栈

• 因为是要找到 x 左边第一个比 x 小的数, 所以所有的数可以升序放进栈里, 每次入栈一个数的时候, 都要使得栈顶元素比他小, 然后每次栈顶元素就是 x 左边第一个比他小的元素. 如果栈是空的话, 说明没有元素比他小.

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt;

int main() {
    int n;
    cin >> n;

    while (n -- ) {
        int x;
        cin >> x;

        while (tt && stk[tt] >= x) tt --;
        if (!tt) cout << "-1" << ' ';
        else cout << stk[tt] << ' ';
        stk[ ++ tt] = x;
    }

    return 0;
}