Skip to content

406. Queue Reconstruction By Height

难度: medium

刷题内容

原题连接

内容描述

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意： 总人数少于1100人。

示例 1:

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解题方案

思路 1 **- 时间复杂度: O(N²)*- 空间复杂度: O(N)***

贪心算法 思路 个子矮的人的位置不会影响到其他人，他的位置不会影响到其他人。

操作步骤 1. 对人群排序，由高到低，身高相同再由低到高 2. 建立一个空队列 3. 对排序后的人群进行遍历，将当前遍历的人 按照他的索引（n）插入到队列第n的位置

代码：

var reconstructQueue = function(people) {
  people.sort((a, b) => ((b[0] - a[0]) || (a[1] - b[1])));
  let queue = [];
  people.forEach(person => {
    queue.splice([person[1]], 0, person);
  })
  return queue
};
回到顶部