思想
单调栈
思路
核心代码
for(int i = 0; i < n; i++){
while(tt > 0 && stk[tt] >= x){
tt--;
}
if(tt != 0)
System.out.print(stk[tt] + " ");
else
System.out.print(-1 + " ");
stk[++tt] = x;
}
完整代码
import java.util.Scanner;
public class Main{
static int N = 100010;
static int m;//接收用户输入的操作次数
static int x;//接收用户输入的数字
static int[] stk = new int[N];//定义栈,存放用户输入的数字
static int tt;//栈的下标
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
//初始化栈的下标
tt = 0;
for(int i = 0; i < m; i++){
x = sc.nextInt();
//tt > 0, 防止栈为空; stk[tt] >= x, 判断栈顶元素是否满足小于x
//循环在找到栈顶元素小于x的时候停止,同时不进行删除操作,进入输出操作
while(tt > 0 && stk[tt] >= x){
//如果栈顶元素不小于x,则不满足题目条件,则删除栈顶元素
tt--;
}
//当栈顶元素不为0, 说明x左边有比x小的数,输出栈顶元素,没有输出-1
if(tt != 0)
System.out.print(stk[tt] + " ");
else
System.out.print(-1 + " ");
//将输入的元素插入到栈中, 一定要最后插入, 输入完全部x再插入是不对的,可以自己演示
stk[++tt] = x;
}
//所有判断结束后,stk[tt]中的数据变成严格上升的序列
/*for(tt = 0; tt < 10; tt++){
System.out.println(stk[tt]);
}
*/
}
}