题解 | 栈和排序

//如果每次循环都用一次Collections.max(intArr.subList(i,N))的话，
//时间复杂度是N**2，但是，
//如果提前先用反向循环设计一个最大值数组，时间复杂度就是N
//即，intArr数组的最后一位肯定是这个（N,N）里最大的，所以从右往左推，用Math.max判断，maxArr每个切片的最大值
import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(System.out);
        int N=Integer.parseInt(br.readLine());
        ArrayList<Integer> intArr=new ArrayList<>();
        String[] arr=br.readLine().split(" ");
        int[] maxArr=new int[N];
        for(String i:arr){
            intArr.add(Integer.parseInt(i));
        }
        maxArr[N-1]=intArr.get(N-1);
        for(int i=N-2;i>=0;i--){
            maxArr[i]=Math.max(maxArr[i+1],intArr.get(i));
        }
        Stack<Integer> sk= new Stack<>();
        for(int i=0;i<N;i++){
            int A=intArr.get(i);
            //原来的：sk.empty()&&A!=Collections.max(intArr.subList(i,N))
            if(sk.empty()&&A!=maxArr[i]){
                sk.push(A);
            }else{
                //原来的：int max=Collections.max(intArr.subList(i,N));
                int max=maxArr[i];
                if(A<max||i==N-1){
                    sk.push(A);
                }else{
                    if(i!=N-1||sk.empty()){pw.print(A+" ");}
                    else{pw.print(A);}
                }
            }
        }
        while(sk.size()!=1&&sk.size()!=0){
            pw.print(sk.pop()+" ");
        }
        pw.print(sk.pop());
        pw.flush();
    }
}