题目描述

模板题
可以看看下面这位大佬画的图
https://www.acwing.com/solution/content/27437/

适用场景：
找左边第一个小于自己的数 1至n
找右边第一个小于自己的数 n至1

找右边第一个大于自己的数 n至1
找左边第一个大于自己的数 1至n

找左边第一个比自己小的数 （对于右边，就算换枚举顺序）

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        int[] stk  = new int[100010];
        int tt = 0;

        for(int i = 1 ; i <= n ;  i++ ){
            int x = scan.nextInt();
            //如果栈不为空且栈顶元素大于等于x，那么就说明栈顶这个数不行，
            //因为比较的是左边第一个最近最小的数，所以就把stk[tt]弹出了；
            while(tt!=0 && stk[tt] >= x){
                tt--;
            }
            //如果弹出操作完了之后，栈不是空的，就输出栈顶元素，
            if(tt > 0) System.out.print(stk[tt]+" ");
            //否则就是栈是空的，输出-1
            else System.out.print("-1" + " ");
            //最后将x插入栈顶；
            stk[++tt] = x;
        }
    }
}

找右边第一个比自己大的数（对于左边，就算换枚举顺序）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] s = new int[n + 1];
        int[] stk = new int[n + 1];
        int[] m = new int[n + 1];
        int tt = 0;

        for (int i = 1; i <= n; i++) {
            s[i] = scanner.nextInt();
        }


        for (int i = n; i >= 1; i--) {
            while (tt > 0 && stk[tt] <= s[i]) {
                tt--;
            }
            if (tt > 0) {
                m[i] = stk[tt];
            } else {
                m[i] = -1;
            }
            stk[++tt] = s[i];
        }

        for (int i = 1; i <= n; i++) {
            System.out.print(m[i] + " ");
        }
    }
}