[LeetCode]406. Queue Reconstruction by Height

Posted by Leo Eatle on 2017-01-11

Question

这道题很有意思,给一个包含Person对象的list,每个person有两个值[h,k],h代表这个人的高度,k代表这个人前面有多少个比他高或者高度一样的人
我们需要重新让他们排队,构建一个符合这个要求的队列
比如:
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Thinking

这道题排名第一的dicussion有一个python解法,他是先把list按照h由高到低排序,然后再按照k分别插入到一个新的list中,而k的值正是插入队列的index,然而我并没有看懂为什么这样做就能获得正确结果。

第二个答案解释得非常清楚

原来这是利用了一个关系:高的人不需要考虑矮的人是否在他们前面,所以我们先安排高的人按照他们的k值插入队列,然后再按照k值插入矮的人,这样后面插入的矮的人对于高的人其实是“隐形”的

Code

class Solution(object):
def reconstructQueue(self, people):
"""
:type people: List[List[int]]
:rtype: List[List[int]]
"""
if not people:
return []
queue = []
for h, k in sorted(people, key=lambda (h, k): (-h, k)):
queue.insert(k, [h , k])
return queue

PS: 这里利用了一个匿名lambda函数表达式简化了list的排序操作