LeetCode 筆記 - 406. Queue Reconstruction by Height
題目在此 406. Queue Reconstruction by Height
給定一群人的身高與條件,people[i] = [hi, ki]
h
是身高,k
是前面必須有 k
個跟他一樣高或比他高的人
請給出符合條件的順序
解題思維
這題的 hint 說從最矮的開始思考,但筆者覺得從高的思考比較順
首先先把題目排序,高的在前面,一樣高的就需要比較少人在前面的人
排前面
因此排序的式子可以寫成這樣
1 | people.sort(key=lambda x : (-x[0], x[1])) |
此時就可以按照 k
把每個人放進答案序列的第 k
個位子
因為從最高的開始放,所以之後就算有其他人放到較高的人前面,也不會影響條件
我們來用 Exmaple 1 來演示一下
1 | # after sorting |
程式碼
1 | class Solution: |