406. 根据身高重建队列
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示,其中h是这个人的身高,k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
注意:
总人数少于1100人。
示例
1 | 输入: |
解题思路
将该队列 按照身高降序,k升序排序
k升序排序是显而易见的,但是身高为什么要降序呢?
这样做就方便从左到右遍历插入排序了
因为只要按照索引插入,前面的身高肯定比当前索引的元素高
代码
1 | public class ReconstructQueue406 { |