Leetcode 406. 根据身高重建队列

心路历程：

看到二维数组的排序问题，第一反应想到了之前合并区间那道题先对数组按照第一维排序，后来在纸上模拟后发现，如果按照第一维度降维，第二维度升维的方式排序，那么后面插入的元素一定不会影响前面的元素。因为一个数只关系比他大或者和他相等的数，如果和他相等那么第二维度越大越靠后。

一直以为这道题是个类似单调栈的题，结果是个二重的贪心题目。

注意的点：

1、list.sort(key = lambda x: (-x[0], x[1]))大法可以多维度排序，但是注意需要返回元组
2、oneDlist.sort(key = lambda x : -x)也可以代表降序

解法：二重贪心

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 从大到小进行插入，因为小的值不会影响之前插入的大的值的正确性；
        people.sort(key=lambda x: (-x[0], x[1]))  # 先按x[0]降序，再按x[1]升序
        res = []
        for i in range(len(people)):
            res.insert(people[i][1], people[i])
        return res