【LeetCode Top 100】406. Queue Reconstruction by Height【Medium】【JAVA】

ゝ一世哀愁。 2021-09-21 04:58 188阅读 0赞

## 1. 题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]

## 2. 题意 ##

有 n 个 (h, k) 对，h 代表高度，k 代表这个对在队列中的位置，在它的位置前面，有 k 个对的高度，比它高或等高。例如 (7, 0)，代表其高度为 7，在它前面有 0 个高度不小于它的对。(4, 4) 代表其高度为 4，在它前面有 4 个高度不小于它的对。

## 3. 思路 ##

这道题，官方的提示是：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]  
让你去找出最小高度的数的位置。

首先，`我们先假设没有相同高度的对存在`，如果我们插入某个对 (h, k) 的时候，队列中已经存在的对，高度都比它高，那么，这个对是不是就应该直接插入在第 k 个位置上。例如假设现在有 (5, 0), (4, 1), (5, 1), 我们插入 (3, 2)，相当于，我们应该将它放置到两个对之后，因为它前面需要有 2 个比它高的对，因此，插入：(5, 0), (4, 1), (3, 2), (5, 1), 我们可以发现是满足题意的。`那么相当于对于不同高度的组，我们可以采用由高到低的顺序，按照 k 值进行插入的方式进行`。

接下来，我们考虑对于`相同高度的对`，对于题目中的要求，k 代表的是大于或者等于的高度的数目，相当于，对于两个相同高度的组，第二个插入的组，第一个组与其他原先存在的比其大的组没有不同。因此，我们`应当将 k 值大的，放在后面进行插入`。例如 (5, 0), (4, 1), (5, 1)，我现在有 (3,0), (3,2)，假设我们先插入 k 值大的，插入结果为：(5, 0), (4, 1), (3,2), (5, 1)，没有问题，此时我们再插入 (3,0)，变成 (3,0), (5, 0), (4, 1), (3,2), (5, 1)，此时就出现了问题，(3, 2) 的对，前面有 3 个对的高度比它高。而如果我们先插入 k 值小的，再插入 k 值大的时，是在其后面，不会影响该值。因此，为了防止相同高度的对插入时不同 k 值的互相影响，因此，我们应当将 k 值大的，放在后面进行插入。

## 4. 解题代码 ##

public int[][] reconstructQueue(int[][] people) { 
    		// 根据上面的分析进行排序
    		// 对于相同高度的，按照 k 值小的在前面
    		// 对于不同高度的，按照 h 值高的在前面
            Arrays.sort(people,
                    (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
    
    		// 排序后，按顺序插入，插入时注意按 k 值插入
            ArrayList<int[]> list = new ArrayList<>();
            for (int[] p : people
            ) { 
                list.add(p[1], p);
            }
            return list.toArray(new int[people.length][]);
        }

## 5. 运行结果 ##

![在这里插入图片描述][20200322001806634.png]

## 6. 相关链接 ##

[本题代码的github链接][github]  
[其他 LeetCode 题目解析][LeetCode]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/b6398156c94141ffb9cf2ad3c58f577c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]: /images/20210920/0da9f8dca1e44d849de6565354c1461a.png
[20200322001806634.png]: /images/20210920/eea74c596d5e4d288dfa3594f1cbbe0d.png
[github]: https://github.com/Parallelline1996/Leetcode/blob/master/Problems/src/main/java/page5/N406_QueueReconstructionByHeight.java
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html