Leetcode 406. Queue Reconstruction by Height -

給定一個由整數組成的二維數組，其中每個數組都表示一個人，其中第一個元素為該人的身高，第二個元素為該人在隊列中的排列順序。按照這種順序重建隊列。意思是把大家重新排列，而每個人前面都只能站比自己高或一樣高的 k個人，這樣的情況下要怎麼排？

Python

方法：排序+貪心

按照身高從高到低排序，身高相同則按位置從小到大排序，因為無論矮的人排在哪裡，都不會影響高的人，所以就按照排序的結果，按順序把每個人插入到相應的位置

按照身高從高到低排序。對於每個人，在它前面插入k個空位置，返回新的隊列。

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1])) #先排ki 再排hi
        res = []
        for p in people:
            res.insert(p[1], p) 
        return res

Python

相關