（js）leetcode 406. 根据身高重建队列

痛定思痛。 2022-12-21 15:50 139阅读 0赞

最近感觉到自己在算法知识方面的匮乏，所以从今天起，每天一题leetcode，今天就先将flag立在这了。

### 题目： ###

> 假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(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\]\]

刚看到题目的时候，我开始怀疑自己的语文水平了，咋就从一个输入队列转换为输出队列了呢。

在自己开始怀疑人生的前一刻，终于理解了题目的意思。

很简单，就是题目的第一句话，整数对(h, k) 代表一个人，h是身高，k是在这个人前面有多少个身高大于等于h的人。

然后，将无序的一组人，按照上面的规则排序。

### 思路： ###

> 1. 将所有人的身高从高到矮排序，即按 h 从大到小排序
> 
> 2. 身高相同的人，按照人数从小到大排序，即按 k 从小到大排序，因为 k 越大，说明排在这个人前面的人越多，这个人的位置越靠后
> 
> 3. 按照1、2排序完之后，依次将每个人放入队列中，当放入第 i 个人时，(下面这两步是官方解答的思路，可在leetcode题解中看到)
> 
>     链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode-sol/
> 
>     1) 第 0,..., i-1, 个人已经在队列中被安排了位置，他们只要站在第 i 个人的前面，就会对第 i 个人产生影响，因为他们都比第 i 个人高；
> 
>     2) 而第i+1,⋯,n−1 个人还没有被放入队列中，并且他们无论站在哪里，对第 i 个人都没有任何影响，因为他们都比第 i 个人矮。
> 
> 也就是后插入的矮的人，不会影响到已经在队列中的高的人，对队列中已存在数据的 k 值没有任何影响作用
> 
> 4. 经过 3 分析可知，采用「插空」的方法，依次给每一个人在当前的队列中选择一个插入的位置。
> 
>   就是，每次插入第 i 个人时，要使得他的前面恰好有 ![k\_\{i\}][k_i] 个人即可  
>

### 代码实现： ###

/**
     * @param {number[][]} people
     * @return {number[][]}
     */
    var reconstructQueue = function(people) {
        // 排序
        people.sort((person1,person2)=>{
            if(person1[0] != person2[0]) {
                // 按照身高从大到小排序
                return person2[0]-person1[0];
            } else {
                // 按照人数从小到大排序
                return person1[1]-person2[1];
            }
        })
        let ans = [];
        people.forEach(person=>{
            // 在第 ki 个位置插入当前人，使得他前面恰好有 ki 个人
            ans.splice(person[1],0,person)
        })
        
        return ans;
    };

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70][]

[k_i]: https://private.codecogs.com/gif.latex?k_%7Bi%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201116231626282.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl,size_16,color_FFFFFF,t_70