https://leetcode-cn.com/problems/queue-reconstruction-by-height/
难度：中等
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
注意：
总人数少于1100人。
示例
输入: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
通过观察，我们可以知道，对于一组数据，如示例中的 (7,0) 和 (7,1)，无论它们所处的位置在哪，在最终结果中，它们的相对位置是不会发生变化的：(7,1) 一定会在 (7,0) 的后面，可能中间隔了一个、可能隔了 n 个。
因此，我们可以先对这组数据排序，先保证它们的相对位置，具体做法是根据 (h, k) 来排序：我们先按 h 从大到小进行排序，这样保证了对于每一个数 i，它前面的数字都不会小于自身，然后对于 h 相同的数字，按 k 从小到大排序，这样，对于 h 相同的数据，它们的相对位置开始就是正确的。
之后，遍历这组排序过的数据，我们使用 tuple 来表示一个 (h, k) 对，遍历过程中，数组索引 i 能够表示不小于当前 tuple 的所有 tuple 的个数（因为我们提前按 h 进行排序了），这样，我们只要根据每个 tuple 的 k 来进行调整即可。
具体调整方法是：对于当前的 tuple ，若 k < i ，说明在当前 tuple 前面的位置，比它高的 tuple 个数太多了，需要将这个 tuple 向前调整 i-k 个位置，让其前面的 tuple 个数刚好等于 k，也就是移动到第 k 个位置。且这样调整并不会影响到已调整的序列，因为那些数据的相对位置并不会发生改变。
JS 代码：
/** * @param {number[][]} people * @return {number[][]} */ var reconstructQueue = function(people) { if (people.length < 2) { return people; } let res = []; // 先根据 h 和 k 排序，主 h 副 k , h 从大到小排序，k 从小到大排序 people.sort((a, b) => { if (a[0] === b[0]) { return a[1] - b[1]; } return b[0] - a[0]; }); for (let i = 0; i < people.length; i++) { let k = people[i][1]; if (k < i) { res.splice(k, 0, people[i]); } else { res[i] = people[i]; } } return res; };（第 27/37 个 case 会超时）
主要思路是先找到序列的第一个 tuple ，然后根据每个 tuple 的 h 和 k 找到插入的位置，所有数据都插入完成之后，有些 tuple 会因为插入操作而导致站位错误，因此需要逐个检查判断是否站错，若站错，则将这个 tuple 重新插入，反复执行此操作，直到所有数据都满足站位要求：
/** * @param {number[][]} people * @return {number[][]} */ var reconstructQueue = function(people) { if (people.length < 2) { return people; } let res = []; let n = people.length; let first; let tuple, k, height, insertIndex; // 先进行第一次排序 for (let i = 0; i < n; i++) { tuple = people[i]; k = tuple[1]; height = tuple[0]; insertIndex = 0; if (k === 0) { while(insertIndex < res.length && res[insertIndex][0] < height) { insertIndex++; } res.splice(insertIndex, 0, tuple); } else { while(insertIndex < res.length && k > 0) { if (res[insertIndex++][0] >= height) { k--; } } res.splice(insertIndex, 0, tuple); } } let flag = true; while(flag) { flag = false; for (let i = 0; i < n; i++) { tuple = res[i]; k = tuple[1]; height = tuple[0]; if (k !== 0) { // 遍历当前 tuple 前面的人，看是否满足 k 的要求 for (let j = 0; j < i; j++) { let tuple1 = res[j]; if (tuple1[0] >= height) { k--; } } if (k !== 0) { k = tuple[1]; // k 要重新赋值，用于下面的重新插入 res.splice(i, 1); // 将错误的 tuple 从结果中移除 flag = true; // 需要再次判断 break; } } } // 若存在错误的站位，则重新插入，且 k 、height 和 tuple 可以就使用之前的 if (flag) { insertIndex = 0; while(insertIndex < n-1 && k > 0) { if (res[insertIndex++][0] >= height) { k--; } } res.splice(insertIndex, 0, tuple); } } return res; };