leetcode-406 根据身高重建队列

题目

https://leetcode-cn.com/problems/queue-reconstruction-by-height

假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(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]]

思路

首先，大体上按照身高由大到小的顺序进行排序，来保证之后插入的时候我们目标数组的每一个元素都大于我们要插入的元素。之后就好办了，根据前面有几个比他高的人来判断我要将新元素插入到哪个位置，比如前面没有比他高的人自然就插入到最前面的位置，python的insert函数就像量身为其打造一般。

还有一点需要注意，在身高相同的情况下，前方比本身身高高的人数少的要排在前面。假如两个人为(x, 0), (x, 1)，那么为了让后面的人找到比他高的人（也就是（x, 0）），那么就需要先将（x, 0）插入其中。不是最高身高的情况也是类似的。

于是，我们就需要进行两次排序，像箱子排序一样。所幸，python的sort函数是稳定的，于是我们就先将前方人数进行升序排序，再将身高进行降序排序。之后逐一插入就大功告成了

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 先按照身高排序，然后按照k升序排
        # 最后进行index 插入
        people.sort(key = lambda x: [-x[0], x[1]])
        res = []
        for p in people:
            res.insert(p[1], p)  # 基于后面的值作为index 插入到list中
        return res