1.思路

这题有两种解法，数组模拟栈+java栈。数组模拟栈速度更加的快，java栈的话封装好了基本方法，使用起来更加高效吧。两种方法本质都一样，只是一个封装了，一个没有封装。

我们来讲一讲这题的具体思路。题目要求找到每个数左边第一个比他小的数。这里就会想到要用单调栈（因为栈是先进后出，这样就好找到左边第一个数），我们如果要找一个元素左边的第一个比他小的数，那我们可以从当前元素开始，从右往左看前面比他小的第一个数，如果左边要比较的数比当前元素大，我们可以发现左边要比较的数不可能是当前元素后面的元素的左边第一个比他小的数，因为我们现在的当前元素比要比较的元素值小并且位置比要比较的元素靠右。所以如果左边要比较的数比当前元素大我们就可以弹出栈；而当遇到左边要比较的数比当前元素小我们就可以输出要比较的元素。

我们可以发现栈中是按从大到小的顺序存储的，所以就叫做单调栈。

2.代码模板

方法一：java栈
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Deque<Integer> stack = new LinkedList<>();
        for(int i = 0; i < n; i++) {    
            int t = in.nextInt();
            while(!stack.isEmpty() && t <= stack.peek())    //如果栈不为空，就看栈顶元素是否大于等于t，如果大于t就弹栈；否则该数就是t左边第一个小于t的数
                stack.pop();
            if(stack.isEmpty()) //如果栈为空就代表t左边没有小于他的数
                System.out.print("-1 ");
            else 
                System.out.print(stack.peek() + " ");
            stack.push(t);  //将t加入栈
        }
    }
}
方法二：数组模拟栈
import java.util.*;
public class Main {
    static int N = 100010;
    static int[] stk = new int[N];
    static int tt;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n --> 0){
            int x = in.nextInt();
            while (tt != 0 && stk[tt] >= x) 
                tt -- ;
            if (tt == 0) 
                System.out.print("-1 ");
            else 
                System.out.print(stk[tt] + " ");
            stk[++tt] = x;
        }
    }
}

3.复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)