【LeeCode】406. 根据身高重建队列

【题目描述】

假设有打乱顺序的一群人站成一个队列，数组 ​​people​​​ 表示队列中一些人的属性（不一定按顺序）。每个 ​​people[i] = [hi, ki]​​​ 表示第 ​​i​​​ 个人的身高为 ​​hi​​ ，前面 正好 有 ​​ki​​ 个身高大于或等于 ​​hi​​ 的人。

请你重新构造并返回输入数组 ​​people​​​ 所表示的队列。返回的队列应该格式化为数组 ​​queue​​​ ，其中 ​​queue[j] = [hj, kj]​​​ 是队列中第 ​​j​​​ 个人的属性（​​queue[0]​​ 是排在队列前面的人）。

​​​​https://leetcode.cn/problems/queue-reconstruction-by-height/description/?favorite=2cktkvj​​

【示例】

【代码】​​从高到低考虑​​

package com.company;
import java.lang.reflect.Array;
import java.util.*;

// 2022-02-18
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        int len = people.length;
        // 排序前: 
        for (int[] person : people) {
            System.out.print(Arrays.toString(person));
        }

        // 按身高倒序, 身高相同则升序
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]){
                    // 如果第一位不同, 则按首位降序
                    return o2[0] - o1[0];
                }else {
                    // 如果第一位相同, 则升序
                    return o1[1] - o2[1];
                }
            }
        });
        // 排序后: 
        System.out.println();
        for (int[] person : people) {
            System.out.print(Arrays.toString(person));
        }

        List<int[]> list = new ArrayList<>();
        // 按下标p[i] 插入list
        for (int[] p : people){
            // 按下标p[1], 添加元素p
            list.add(p[1], p);
        }
        System.out.println();
        for (int[] x : list){
            System.out.print(Arrays.toString(x));
        }
        return list.toArray(new int[list.size()][]);
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().reconstructQueue(new int[][]{{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}}); // 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
        // new Solution().reconstructQueue(new int[][]{{6,0},{5,0},{4,0},{3,2},{2,2},{1,4}}); // 输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
    }
}