一、题目

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] 是排在队列前面的人）。


[来源：https://leetcode-cn.com/problems/queue-reconstruction-by-height/]

二、思路

我们的思路是从低至高考虑：

1. 定义排序规则：身高低肯定靠前，同身高人数多肯定靠后。
2. 取出排好序的数组 + 检测空位下标是否正确（插空）
3. 一旦插空，该位置不再计入空位。

下面，我们举例说明：

输入：[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

至此，重建身高队列完毕！

三、代码

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        //：插空法：从低到高考虑
        //实现Comparator接口（规则排序）
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] person1, int[] person2) {
                //定义排序规则：身高低肯定靠前，同身高人数多肯定靠后（先确定它）
                if (person1[0] != person2[0]) { //不同身高，按身高从低到高排列
                    return person1[0] - person2[0];
                } else {    //同身高，按人数从高到低排列
                    return person2[1] - person1[1];
                }
            }
        });
        //记录长度
        int n = people.length;
        //记录结果集
        int[][] result = new int[n][];
        //循环：取出排好序的数组（寻找空位）
        for (int[] person : people) {
            //记录所属空白数量（下标从0开始，须+1，保证可以寻找到正确空位下标）
            int spaces = person[1] + 1;
            //循环：寻找空位
            for (int i = 0; i < n; ++i) {
                //位置null代表空位，可以进行操作，否则i++，寻找后面的位置
                if (result[i] == null) {
                    //不是空位，spaces--，每执行一次本操作，就会离所属空位更近一步
                    --spaces;
                    //检测空位下标是否正确
                    if (spaces == 0) {
                        result[i] = person;
                        break;
                    }
                }
            }
        }
        //返回结果
        return result;
    }
}