牛客网真题-92-最小排列

用优先级队列保存正确顺序，如果存在有一个不在正确顺序上就往后找它在哪，然后交换
值得注意的是，如果全部都在正确的顺序，即原排列时一个递增数列，那么也是要进行一次交换，交换最后两个

import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] ints = new int[n];
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0; i < n; i++){
            ints[i] = scanner.nextInt();
            queue.add(ints[i]);
        }
        boolean flag = false;
        int temp = -1;
        for(int i = 0; i < ints.length; i++){
            if(!flag){
                if(ints[i] != queue.peek()){
                    temp = ints[i];
                    ints[i] = queue.peek();
                    flag = true;
                }else{
                    queue.poll();
                }

            }else{
                if(queue.peek() == ints[i]){
                    ints[i] = temp;
                    break;
                }
            }

        }
        //必须进行一次交换
        if(!flag && ints.length >= 2){
            int tem = ints[ints.length - 1];
            ints[ints.length - 1] = ints[ints.length - 2];
            ints[ints.length - 2] = tem;

        }
        //打印
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < ints.length - 1; i++){
            res.append(ints[i]).append(" ");
        }
        res.append(ints[ints.length - 1]);
        System.out.println(res);
    }
}