题目描述

单调栈

JAVA 代码

import java.util.*;
import java.io.*;

class Main{
    static final int N = 100010;
    static int[] stk = new int[N];
    static int tt = -1;

    public static void main(String args[])throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());

        int[] a = Arrays.asList(in.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();
        for(int i = 0; i < n; i ++ ){
            int x = a[i];
            //将单调栈中 >= x元素全部清除. 
            while(tt != -1 && stk[tt] >=x ) tt--;

            //如果有小于 x 的元素,则输出,否则为-1;
            if(tt != -1){
                System.out.print(stk[tt] + " ");
            }else{
                System.out.print("-1 ");
            }
            //将x push 入栈
            stk[++tt] = x;
        }

    }

}