# 根据身高重建队列
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对`(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]]
```

## 题解

```javascript
/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = function(people) {
    // people.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
    people.sort((a, b) => a[0] - b[0]);
    const n = people.length;
    let target = [];
    people.forEach((v) => {
        let spaces = v[1] + 1;
        for(let i=0;i<n;++i){
            if(target[i] === void 0 || target[i][0] === v[0]){
                spaces--;
                if(spaces <= 0 && target[i] === void 0){
                    target[i] = v;
                    break;
                }
            }
        }
    })
    return target;
};
```

## 思路
当每个人的身高都不相同时，我们将他们按照身高从小到大进行排序，之后使用插入的方式进行还原，首先我们假设有`n`个人，然年后我们将要插入第`i`个人，现在第`0 ... i-1`已经排好了位置，无论他们如何站队，对我们将要插入的第`i`个人都没有影响，对于第`i ... n-1`个人，只要插入的位置在第`i`个人前，就能够对第`i`个人产生影响，之后我们就可以建立一个长度为`n`的数组，对排序过后的数组将其分别插入，那么当我们插入第`i`个人时，其要插入的位置必定是其高度大于它的数量`+1`，例如我们第一个要插入的是`(5, 2)`，那么他的位置就是`<empty>, <empty>, (5, 2)`，也就是说给他安排的空位是第三个位置，此外由于其是队列的第一个数值，其后的值必定比他大，所以其后的值按照同样的规则进行插入是可以满足条件的，在这里需要特殊处理一下身高相同的人，如果身高相同，同样应该将其作为一个空位去处理，之后特殊处理这个位置如果是空位则直接插入，否则插入到其后边的位置。在官方给出的题解是在排序的时候根据身高升序，在根据前边身高高于他的人的数量进行降序，之后就可以直接进行上述规则而不用特殊处理相等的情况，举个例子，当我们根据上述的排序规则进行排序后得到`(5, 2) (5, 0) ...`，那么先插入`(5, 2)`，再插入`(5, 0)`可以得到`(5, 0), <empty>, (5, 2)`，当然我们经过特殊处理相同的情况也是可以得到的，但是如果不经过特殊处理则会得到`(5, 0), <empty>, <empty>, (5, 2)`显然是不合适的。首先进行排序，这里只是按照身高进行排序，之后取得数组长度`n`，定义目标数组，遍历排序过后的数组，定义好应该取得的空位置并`+1`，之后进行`n`次循环，如果这个位置未定义或者值与要插入的值相同，那么就将应该减少的空位置数量`-1`，如果应该置入的空位置数量小于`0`并且这个位置是空，那么就将该值插入该位置并结束内层循环，最后返回目标数组即可。

## 每日一题

```
https://github.com/WindrunnerMax/EveryDay
```

## 参考

```
https://leetcode-cn.com/problems/queue-reconstruction-by-height/
```