单调栈经典例题

发布时间:2024年01月24日

?


import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        //单调递增栈,栈中的所有元素严格单调递增
        //比如1 6 5 4 9 8 7 10 11 56不会出现在答案里
        //因为被4给拦截住了
        //遍历到4的时候可以把56都出栈
        //89也不会出现,被7拦住了
        //遍历到7的时候可以把89出栈
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] stack = new int[100010];
        int tt = 0;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            //栈顶元素>=当前遍历到的元素就得出栈,出栈的元素以后都不会出现在答案里
            while (tt != 0 && stack[tt] >= x){
                tt--;
            }
            //退出循环时的栈顶就是要输出的结果
            if (tt != 0) System.out.print(stack[tt] + " ");
            else System.out.print("-1 ");

            //最后把该数放进栈里
            stack[++tt] = x;
        }
    }
}

文章来源:https://blog.csdn.net/2302_76649176/article/details/135826851
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。