406. 根据身高重建队列（中等）

406. 根据身高重建队列

• 1. 题目描述
• 2.详细题解
• 3.代码实现
• • 3.1 Python
  • 3.2 Java

1. 题目描述

题目中转：406. 根据身高重建队列

2.详细题解

    做一道题之前先静心，默念三遍一切反动派都是纸老虎。已知一个队列，队列中每个数据表示一个属性，[hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人，该题要求将打乱顺序的队列恢复队列顺序。
  对于一个属性[hi,ki]，如果前面的属性身高均大于等于hi，那么属性[hi, ki] 应该在队列的索引为ki，但因前面存在低于该身高的属性，因此实际索引并不为该值。 那该如何解决上述问题呢？现在问题的关键是前面可能存在低于该升高的属性，如果能解决此问题，那么该问题则迎刃而解非常简单了。
  应当如何避免上述问题，如果我们始终按照身高由高到底的顺序恢复顺序，那么对于当前身高来说，前序的升高均不低于该升高，此时即可按照索引位置插入了，即采用贪心策略，贪心的先恢复当前队列最高身高属性的位置，对于当前[hi,ki]来说，当前已恢复队列中的升高均不低于hi，因此ki即为[hi, ki]对于此时队列所在的索引位置。故算法如下步骤如下：
   1.按身高降序排列，身高相同的，按属性值升序排列，为什么呢？
   2.按照身高降序的顺序依次放入队列中，对于第i个人，因为其身高小于等于前面0到i-1的人的身高故第i个人插入的位置并不会影响前面人的属性，因为第i个人前面有kj个人，故插入索引kj处。
  3.注意2中临界条件，当第i个人身高与0到i-1的人身高相同时，第i个人的插入位置则会影响前面人的属性，除非第i个人的位置比所有0到i-1人中同他身高相同的人的位置更靠后，这就回答了1中身高相同的，为什么要按照属性升序排列

3.代码实现

3.1 Python

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x:(-x[0], x[1]))
        ans = [people[0]]
        for x1, x2 in people[1:]:
            ans.insert(x2, [x1, x2])
        return ans

3.2 Java

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 使用 Comparator 对数组进行排序，按照 x[0] 降序，x[1] 升序
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0]) {
                    return a[1] - b[1];
                }
                return b[0] - a[0];
            }
        });

        // 使用 LinkedList 存储结果
        List<int[]> ansList = new LinkedList<>();
        for (int[] person : people) {
            ansList.add(person[1], person); // 在位置 person[1] 插入 person
        }

        // 将 LinkedList 转换为二维数组
        int[][] ans = new int[people.length][2];
        for (int i = 0; i < people.length; i++) {
            ans[i] = ansList.get(i);
        }
        
        return ans;
    }
}

  执行用时不必过于纠结，对比可以发现，对于python和java完全相同的编写，java的时间一般是优于python的；至于编写的代码的执行用时击败多少对手，执行用时和网络环境、当前提交代码人数等均有关系，可以尝试完全相同的代码多次执行用时也不是完全相同，只要确保自己代码的算法时间复杂度满足相应要求即可，也可以通过点击分布图查看其它coder的code