【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]]
    }
}