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

本文主要是介绍406. 根据身高重建队列（中等），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

这篇关于406. 根据身高重建队列（中等）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---