题解 | 栈和排序

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		Deque<Integer> stackDeque=new ArrayDeque<>();
		int n=scanner.nextInt();
		int a[]=new int[n];
		for (int i = 0; i < a.length; i++) {
			a[i]=scanner.nextInt();
		}
		int num=n;//期待的值
		int b[]=new int[n];
		int flag=0;
		for (int i = 0; i < a.length; i++) {
			stackDeque.push(a[i]);
			if(a[i]==num) {
				b[flag]=stackDeque.pop();
				flag++;
				num--;
			}
			
		}
		while(!stackDeque.isEmpty()) {
			b[flag]=stackDeque.pop();
			flag++;
		}
		for (int i = 0; i < b.length; i++) {
			System.out.print(b[i]+" ");
		}

	}

}

这题考的是贪心，一开始想要每一次期待的最大值，所以我们设置一个num，表示它所期待的传入新序列的值，然后当压入栈的值与该值相等时，就出栈，如果所有数字都压入栈了，那么我们就只能把栈中元素逐一输出了