406. Queue Reconstruction by Height

Leetcode link

解题思路

题目要求我们将输入的二维数组 people 按照特定的规律排序

规律是，数组元素的第一项表示当前的人的身高，第二项表示当前的人的前面有几个比他高或者跟他一样高的人

那么我们的思路就是：

• 首先先将所有人按照从低到高排序（因为比较低的人并不会影响到高的人的第二项，所以低的人需要优先排序）
• 其次，如果两个人身高相同，那么在她前面比她高的人多的排在前面（因为第二项比较大的人在身高相同的情况下肯定会比第二项比较小的人更靠后）

综上所述，我们需要对 people[0] 做升序，如果相等，则对 people[1] 做降序

重新排序完数组之后，我们就可以按照排序好的顺序来遍历数组了，具体思路如下：

• 首先我们需要一个长度为 people.length 的数组 res
• 然后我们依序遍历数组 people，按照顺序获取当前元素的第二项 k（k 代表了我们要将它放在数组 res 的第 k 个空元素的位置）
• 接着我们遍历数组 res，找出第 k 个空元素依次放入当前遍历的 people 元素
• 循环第 2、3 步直到数组遍历完毕，最后的 res 数组就是答案

Javascript

/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = function(people) {
    people.sort((a, b) => {
        if(a[0] === b[0]) {
            return b[1] - a[1];
        }
        return a[0] - b[0];
    });

    const res = new Array(people.length).fill(0);
    for(let person of people) {
        let pos = person[1];
        let space = 0;
        for(let j = 0;j < res.length;j++) {
            if(res[j] === 0) {
                if(space === pos) {
                    res[j] = person;
                    break;
                } else {
                    space++;
                }
            }
        }
    }
    return res;
};