LeetCode0406.QueueReconstructionbyHeight根据高度重建队列[Medium][Python][greedy].每个人都由一对整数（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]]问题一群人以随机顺序站在队列中。每个人用一对整数(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]]思路Greedy先按照高度h从高到低，k从小到大排序。然后随便插入，就可以看到代码注释了。这是一个例子：输入：[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]排序：[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]如[6,1]，表示只有一个比6、然后自然插入位置1（从0开始数）：[[7,0],[6,1],[7,1],[5,0],[5,2],[4,4]]等等[5,0]:[[5,0],[7,0],[6,1],[7,1],[5,2],[4,4]][5,2]:[[5,0],[7,0],[5,2],[6,1],[7,1],[4,4]][4,4]:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]end时间复杂度：O(len(people))空间复杂度：O(1)Python代码classSolution(object):defreconstructQueue(self,people):""":typepeople:List[List[int]]:rtype:List[List[int]]"""people.sort(key=lambdax:(-x[0],x[1]))#根据h从高到低，k从小到大排序res=[]forpinpeople:res.insert(p[1],p)#每次在p[1]位置插入p即可，因为p[1]表示只能出现在p之前的数字returnrescodeaddressgithublink
