java---单调栈算法（每日一道算法2022.8.7）

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

输入
运行次数
5
数组内元素
3 4 2 7 5

输出
-1 3 -1 2 2

public class 单调栈 {
    //初始化数据，tt代表stack的指针
    public static int N = 100010, tt = 0;
    public static int[] stack = new int[N];

    public static void main(String[] args) {
        //n拿到运行次数
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        while(n-- > 0){
            //x拿到每一次的元素
            int x = in.nextInt();
            //这里的核心思路就是如果stack的顶部元素大于等于当前元素x，那么就说明x可以替代顶部元素
            //一直循环到stack的顶部元素小于x也就是不能替代为止，或者stack为空就说明当前元素x左侧没有比x小的值，返回-1
            while (tt > 0 && stack[tt] >= x){tt--;}
            if (tt > 0) {System.out.print(stack[tt] + " ");}
            else {System.out.print("-1 ");}
            //每次结束时都将当前元素x加入到stack中
            stack[++tt] = x;
        }
    }
}

代码很短，思路却很抽象且复杂

声明：算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流