6-104-(LeetCode-406) 根据身高重建队列

arctic_fox / 2023-05-03 / 原文

1. 题目

读题

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

考查点

这道题的考查点是贪心算法的应用，以及如何根据题目的要求设计合适的排序规则和插入策略。

贪心算法是一种常见的解决优化问题的方法，

它需要我们证明每次选择最优的局部解可以导致全局最优解。

这道题也可以用动态规划来解决，但是会比较复杂和低效。

2. 解法

思路

这道题目的思路是使用贪心算法，即每次选择最优的局部解，从而得到全局最优解。具体来说，我们可以按照以下步骤：

1. 把所有的人按照身高从高到低排序，如果身高相同，就按照前面的人数从小到大排序。
2. 创建一个空的列表，用来存放结果。
3. 对于排序后的每个人，把他们插入到列表中，插入的位置就是他们前面的人数。
4. 把列表转换成数组并返回。

这样做的原因是，当我们按照身高降序排列时，我们可以保证后面插入的人不会影响前面已经插入的人的相对位置。而当身高相同时，我们按照前面的人数升序排列，这样可以保证同样高度的人按照正确的顺序插入。¹² 有详细的解释和示例。³ 和 ⁴ 是一些关于贪心算法的概念和指导。

具体实现

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // Sort people by height in descending order
        // If two people have same height, sort them by number of people in front in ascending order
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] p1, int[] p2) {
                if (p1[0] != p2[0]) {
                    return p2[0] - p1[0];
                } else {
                    return p1[1] - p2[1];
                }
            }
        });
        
        // Create a list to store the result
        List<int[]> result = new ArrayList<>();
        
        // For each person in the sorted array
        for (int[] person : people) {
            // Insert the person at the index equal to the number of people in front
            result.add(person[1], person);
        }
        
        // Convert the list to an array and return
        return result.toArray(new int[people.length][2]);
    }
}