【LeetCode】【算法】406. 根据身高重建队列

LeetCode 406. 根据身高重建队列

题目描述

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [h_i, k_i] 表示第 i 个人的身高为 h_i ，前面 正好 有 k_i 个身高大于或等于 h_i 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [h_j, k_j] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

思路

参考的题解【先排序，再插队】动画演示算法过程，有点小套路

1. 先做排序，排序思路是h_i降序，k_i升序（这么排序是为了保证正确性，如果k_i是降序排列的话，假设有(5,5)，先插入到队列之后，又插入(5,1)，但此时(5,5)前面排队的人多了一个，就导致不符合我们目标要求）
2. 排序完成后，将结果往list里放，放的规则是：
   I. 如果列表当前长度<k_i的话，直接将这个人插入到列表末尾
   II. 否则将这个人插入到列表的k_i处

代码

class Solution {public int[][] reconstructQueue(int[][] people) {// 第一个元素降序，第二个元素升序Arrays.sort(people, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {if (o1[0] != o2[0]){// 第一个元素不相等，降序排列return o2[0] - o1[0];} else {// 第二个元素升序排列return o1[1] - o2[1];}}});// 排序过后，往结果里放List<int[]> list = new LinkedList<>();for (int i = 0; i < people.length; i++) {if (list.size() < people[i][1]){list.add(people[i]);} else {list.add(people[i][1], people[i]);}}return list.toArray(new int[list.size()][]);}
}