根据身高重建队列

力扣406-根据身高重建队列 (opens new window)

对于这类需要考虑两个维度的题目，解决方法都是优先考虑一个维度。 例如在分发糖果 (opens new window)一题中， 先考虑左侧再考虑右侧这样的做法。

第一步首先将原数组进行排序，排序的原则如下。

• 身高更高的处于前面
• 相同身高时，k更小的处于前面

排序之后的数组有一个特点需要记住，people[i]之前的所有元素身高都大于等于peolpe[i]。 同时这也是为什么需要让k更小的位于队列的前面。

第二步就比较简单了，按要求插入对应元素即可。规则就是，people[i][1]作为people[1]在新队列中的下标。 顺序遍历队列，遍历到people[i]时，它即使被放在队列最后也是符合要求的。题目要求前面有k个大于等于他身高的元素，那么将k作为下标就可以了。 那么会不会出现后插入的元素导致前面插入的元素不符合规则呢？

肯定不会的。首先后插入元素身高一定小于等于先插入的元素；然后再来看k，分三种情况。

1. k大于先插入元素的k。这不会影响到前面的元素，肯定符合条件。
2. k等于先插入元素的k。则会把先插入元素向后挤一个位置，但是它的身高是比先插入元素更矮的，也不影响。
3. k小于先插入元素的k。也是把先插入元素向后挤，也不影响。

还有问题就是，如果身高相同k不同呢？按照我们排序后的队列，身高相同一定是k更小的先插入，所以身高相同时一定会被插入到先插入元素的后面。自然不影响。

var reconstructQueue = function(people) {
    let queue = []
    //原数组排序。身高更高的在前
    people = people.sort((a, b) => {
        if(b[0] !== a[0]){
            return b[0] - a[0]
        }else {
            //相同身高，ki更小的在前
            return a[1] - b[1]
        }
    })

    //遍历数组进行插入
    for(let i = 0; i < people.length; i++) {
        //将ki作为people[i]插入新数组的下标
         queue.splice(people[i][1], 0, people[i])
    }

    return queue
};