📃 题目描述

题目链接：406. 根据身高重建队列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

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

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

🔔 解题思路

对于这种两个维度的情况，一定是要先确定一边，然后再处理另一边：

1. 确定 h：按照身高从大大小排，确保前面人的身高都高于我，若身高一致，则 k 大的人排后面
2. 处理 k：新建一个队列，根据 k 作为下标依次插入队列

举个例子：[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 排序后，[[7,1],[7,0],[6,1],[5,0],[5,2],[4,4]]

新建一个队列 queue，根据排序后的数组依次进行处理：

• 对于 [7,1] 来说，它应该插入现在队列的第 1 个位置，此时队列 [null, [7,1]]
• 对于 [7,0] 来说，他应该插入现在队列的第 0 个位置，此时队列 [[7,0], [7,1]]
• 对于 [6,1] 来说，他应该插入现在队列的第 1 个位置，此时队列 [[7,0],[6,1],[7,1]]，可以看到，[6, 1] 的插入并不会对原本处在第 1 个位置的 [7,1] 有什么影响，因为身高较高的我们已经先处理了，身高较矮的无论你插入在哪里，对身高较高的都不会有任何影响
• ......

最后，queue = [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

• 局部最优：优先按照身高较高的 people 的 k 来插入队列。插入操作过后的 people 满足队列属性
• 全局最优：最后都做完插入操作，整个队列就满足题目要求的队列属性了

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 按照身高从大大小排，确保前面人的身高都高于我
        // 若身高一致，则 k 大的人排后面
        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];
                }
            }
        });

        // 根据 k 执行插入, k 即对应着插入下标
        LinkedList<int[]> queue = new LinkedList<>();
        for (int[] p : people) {
            // public void add(int index, E element);
            queue.add(p[1], p);
        }

        return queue.toArray(new int[people.length][2]);
    }
}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：O(NLogN)