题目内容

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

输入格式

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

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

输出格式

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

数据范围

1≤N≤10^5
1≤数列中元素≤10^9

输入样例

5
3 4 2 7 5

输出样例

-1 3 -1 2 2

题解

单调栈，就是满足栈的性质，同时从栈顶到栈底的元素是严格递增（或者递减）。
在本题中，我们仅需要构造一个单调栈，并每次对栈进行维护，保证单调栈的栈顶满足题目中所给出的要求，即存储左边第一个比当前数小的数。思路如下：
1、当遍历序列的第一个数时，该数在序列最左边，无左边最小的数，因此输出-1，并将当前数字压入栈中
2、继续遍历，当遍历到第n个数时，该数和栈中的元素进行比较，若该数大于等于栈中元素，则对栈进行弹出，直到栈为空或者找到第一个比该数小的元素为止，然后未找到则输出-1，找到则输出栈顶对应的数字。最后，将该数压入栈中。
3、继续重复2，直到全部序列遍历完毕

代码

#include <iostream>
using namespace std;

const int N = 100010;

int n;
int stk[N], tt;

int main(){
    cin >> n;
    for (int i = 0;i < n;i++){
        int x;
        cin >> x;
        while (tt && stk[tt] >= x) tt --;
        if(tt) cout << stk[tt] << ' ';
        else cout << -1 << ' ';
        stk[++tt] = x;
    }
    return 0;
}