题目描述

给定一个长度为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

(算法练习) $O(n)$

对于这个问题 个人觉得最重要的核心就是 单调递减栈和单调递增栈的问题，由题意可以得到找到左边的最近元素
说明栈中的左边应该存储一些比当前元素小的元素 从而判断是是单调递增栈

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n;
int q[N];
int main(){
    scanf("%d",&n);
    stack<int> st;
    for(int i =0;i<n;i++){
        scanf("%d",&q[i]);
    }
    for(int i =0;i<n;i++){
        // 你要想找左边的最小元素 你得保证左边都是小元素 从而这个是严格单调递增栈
        while(!st.empty()&&q[i]<=st.top()){
            st.pop();
        }
        printf("%d ",st.empty()?-1:st.top());// 这个是三元表达式 大家可以去学习一下
        st.push(q[i]);
    }
    return 0;
}

求赞 求关注 谢谢支持！