Leetcode 406-根据身高重建队列

题意

假设有打乱顺序的一群人站成一个队列，数组 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:

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

思路

首先我们需要对完全无序的队列做一些预处理。考虑这样一个排队问题：

有 $n$ 个人，将他们从高到矮排成一队，设排队每个位置上的身高分别是 $h_0,h1,\cdots ,h_{n-1}$ 。

若 $n$ 个人的身高不同，该问题十分简单。但若存在身高相同的人时，我们需要指定一个特殊的排序方式才能排出一个完整的队列。我们可以利用原问题提供的 $k$ 值。设 $h_i=h_j, k_i>k_j$ 。显然，原问题中，身高相同时，$k$ 值越大的人所在位置越靠后，即 $h_i$ 必然会排在 $h_j$ 之后。因此可以设 $h_i = h_j - \delta$ ，其中 $\delta$ 是一个不影响其他身高排序的微小量。这样一来，每个人的身高又可以视为不同的了。

解决这一问题只需要对原序列做这样一个排序：首先按第一分量（身高）降序排列，当第一分量相等时，按第二分量（k）升序排列。

在完成这一排序后，我们再考虑原问题。原问题要求，对于队伍中位置 $i$ 的人，队伍之前身高 $\ge h_i$ 的人数正好为 $k_i$。我们将上一问题排好的顺序重新排入下一个队列。当排入第 $i$ 个人时：

第 $0, \cdots , i-1$ 个人已经在队伍中安排好了位置。他们都比第 $i$ 个人高，因此，只要他们排在第 $i$ 个人前面即可对 $k_i$ 产生影响。
第 $i+1, \cdots, n-1$ 个人都比第 $i$ 个人矮，无论他们站在哪里都不会对第 $i$ 个人产生影响。

因此，我们只要将第 $i$ 个人“插入”当前以排好的队伍，使得其前面正好有 $k_i$ 个人即可。依次处理每一个人，即可得到原问题需要的排序。

代码：

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (o1, o2) -> {
            if (o1[0] == o2[0])
                return o1[1] - o2[1];
            return o2[0] - o1[0];
        });

        List<int[]> ans = new ArrayList<>();
        for (int[] person : people) {
            ans.add(person[1], person);
        }
        return ans.toArray(new int[ans.size()][]);
    }
}