406.根据身高重建队列

链接：406.根据身高重建队列
难度：Medium
标签：树状数组、线段树、数组、排序
简介：假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对 (h, k) 表示，其中 h 是这个人的身高，k 是应该排在这个人前面且身高大于或等于 h 的人数。 例如：[5,2] 表示前面应该有 2 个身高大于等于 5 的人，而 [5,0] 表示前面不应该存在身高大于等于 5 的人。编写一个算法，根据每个人的身高 h 重建这个队列，使之满足每个整数对 (h, k) 中对人数 k 的要求。

题解 1 - typescript

• 编辑时间：2020-11-17
• 执行用时：112ms
• 内存消耗：44.2MB
• 编程语言：typescript
• 解法介绍：[参考链接](https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode-sol/)。

function reconstructQueue(people: number[][]): number[][] {
  people.sort(([h1, k1], [h2, k2]) => (h1 === h2 ? k1 - k2 : h2 - h1));
  const ans: number[][] = [];
  for (const p of people) {
    const [, k] = p;
    ans.splice(k, 0, p);
  }
  return ans;
}