题目
给定一个长度为 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/
本文仅用作学习记录和交流