LeetCode 题解 | 406 号问题：根据身高重建队列
LeetCode 题解 | 406 号问题：根据身高重建队列
今天分享的题目来源于 LeetCode 第 406 号问题：根据身高重建队列。
一、题目描述
假设有打乱顺序的一群人站成一个队列。每个人由一个整数对 (h, k)表示，其中 h 是这个人的身高，k 是排在这个人前面且身高大于或等于 h 的人数。编写一个算法来重建这个队列。
注意：
总人数少于1100人。
示例
输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
二、题目解析
题目输入是一个二维数组，这个数组的元素是被打乱的，每个元素是个二元祖，表示的一个人的身高以及他前面比他高或者和他一样高的人的个数，让你基于此重新排序。
在做这道题之前，先摒弃一个观念就是：在还没有完全想出可行解的时候就去思考时间复杂度。
除非题目对时间复杂度或是输入数据规模有硬性要求，你可以基于题目要求的时间复杂度来思考解题的方向。
但是一般的情况下，我们都是试着先去想出可行解，然后根据可行解一步步的优化，不然的话，你做题很容易就会没有思路，因为你心中你所猜测的那个最优时间复杂度会不自不觉地帮你 排除 很多 “可能的解”。
回到这道题，我们先试着找出可行解。
直觉告诉你这是一个和排序相关的题目，但是这其中的两个变量让排序变得棘手，我们不仅需要考虑身高，还需要考虑前面的人数。
突破口在哪？
当然了，光排序肯定是不够的，我们还需要一些额外的操作，你可以想象一些，我们要对这一堆人（元素）进行排序，每个人都有属于他的位置，我们的工作是将人一个个放到属于他的位置，那我们该怎么放，或是说以一个什么样的顺序去放，才不会出错？
如果我们先放个子矮的是怎么样的情况，考虑例子 [[5,0],[6,0],[7,0]]。
我们先放置元素 [5,0]，将其放在第一个位置，那么接下来考虑 [6,0]，这时就会出现问题，如果光考虑 [6,0] 本身，它其实应该被放在第一个位置，但是问题是如果把 [6,0] 放到第一个位置，之前放置的 [5,0] 就不正确了，那你可能会说，那就把 [6,0] 放到 [5,0] 的后面呗，这个例子下是可以，但是如果例子是 [[5,1],[6,0],[7,0]] 呢？也就是说你考虑当前元素的时候还必须去重新考虑一遍之前放置的元素。
你可以看到，按这样的考虑方式，之前放置的元素会受到当前放置元素的影响。
我们再来看看先放个子高的是怎么样的情况，还是考虑例子 [[5,0],[6,0],[7,0]]，我们先放置元素 [7,0]，放到第一个位置，[[7,0]] 然后放置 [6,0]，还是放到第一个位置，[[6,0], [7,0]]。
你可以看到，按这样的顺序，每当我们考虑一个元素，之前已经考虑过的元素都比当前元素大或是等于当前元素，不管把当前元素放到哪，当前元素的放置均不会对之前已经放置的元素造成影响而出问题，只需要按 “前面比他高的人数” 的值将当前元素插入到指定位置即可。
于是，我们可以采用第二种方式进行插入。这里有个小细节就是，如果两个人的身高相同，我们要先考虑放置人数少的。这一点也很好解释，对于身高相同的人，最后的答案肯定是，人数少的会插在人数多的前面，如果先插人数多的，那么再插人数少的就会对人数多的产生影响，而先插入人数少的就不会有这个问题。
综上所述，这道题的整体思路就是先排序后插入即可，但是你依然可以看到这其中的一些很微妙的思考过程。
三、动画描述
四、参考代码
public int[][] reconstructQueue(int[][] people) {
// 对输入数组基于身高排序（倒序）
// 如果身高相同，基于人数排序（正序）
Arrays.sort(people, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if (a[0] != b[0]) {
return b[0] - a[0];
}
return a[1] - b[1];
}
});
List<int[]> result = new LinkedList<>();
// 基于人数将元素插入到指定位置即可
for(int[] p : people){
result.add(p[1], p);
}
return result.toArray(new int[people.length][]);
}
五、复杂度分析
这道题目，因为插入的关系，最差时间复杂度是 O(n^2)。
至于空间复杂度，因为用了个 list 作为过渡，虽然说没有创建新的数组，但是因为引用的问题，空间复杂度是 O(n)，用些技巧你也可以省去这个复杂度，但这不是重点。
重点是我们能否继续在时间上进行优化呢？
想要继续优化，我们可能需要用到比较高阶的树的知识。
在这先买个关子，感兴趣的话，你可以思考一下，下次我们再重新以另外一个角度来审视这道题，敬请期待，大家加油：）