算法题：根据身高重建队列
今天想聊个有趣的算法题目：根据身高重建队列。这个题目看似简单，但背后却蕴藏了不少有趣的编程技巧和思维挑战。首先，我们来看看题目的要求。
题目要求根据一个队列中的人，按身高重建新的队列。每个人的描述包含两个数字：一个是身高，一个是前面有多少人比自己高。对于某个给定的人，我们的任务是按要求将他们插入到新队列中。很显然，这不仅仅是排序问题，更是一个考察我们如何通过适当的数据结构去插入元素的题目。
题目分析：我们可以这么理解，每个元素的第二个值“前面有多少人比自己高”意味着他在结果队列中的位置，且这个位置是从前往后的。更直观地说，就是他必须站在一个不高于他的人的后面，同时，队列中比他高的人的数量必须符合条件。
这个问题常用的解法是贪心算法配合插入排序的方式来实现。咱们不妨直接看一下代码，如何通过这种方式来解决这个问题。
def reconstructQueue(people):
# 先按身高从高到低排序，身高相同的按照前面的人数从小到大排序
people.sort(key=lambda x: (-x[0], x[1]))
queue = []
# 遍历排序后的列表，将每个人插入到对应的位置
for person in people:
queue.insert(person[1], person)
return queue
解释一下这个代码吧。首先，我们对people进行排序，排序的规则是先按照身高降序排列，如果身高相同，则按照前面的人数升序排列。为什么要这样做？因为如果我们先插入身高高的人，后面的身高较矮的人插入时就可以满足他们所要求的前面有多少人比他们高的条件。
接下来，我们就简单地遍历这个排序后的队列，将每个元素按其指定的位置插入到新队列中。这里使用了insert方法，它会根据给定的索引将元素插入到队列中。这样，队列中的每个人都能根据给定的条件正确放置。
让我们看看一个具体的例子：
假设输入是：
people = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
首先按照排序规则，排序后的people会变成：
[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
然后，我们依次插入到queue中：
插入 [7, 0]，queue = [[7, 0]]插入 [7, 1]，queue = [[7, 0], [7, 1]]插入 [6, 1]，queue = [[7, 0], [6, 1], [7, 1]]插入 [5, 0]，queue = [[5, 0], [7, 0], [6, 1], [7, 1]]插入 [5, 2]，queue = [[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]]最后插入 [4, 4]，queue = [[5, 0], [7, 0], [5, 2], [6, 1], [7, 1], [4, 4]]
最终输出：
[[5, 0], [7, 0], [5, 2], [6, 1], [7, 1], [4, 4]]
这个方法的时间复杂度主要来自于排序和插入操作。排序的时间复杂度是O(n log n)，而insert方法在最坏情况下是O(n)，因此整个算法的时间复杂度是O(n^2)。对于一般的题目来说，虽然时间复杂度略高，但可以应对大部分中小规模的情况。
当然，如果题目规模更大，可能需要优化算法，这时我们可能会考虑使用链表等数据结构来优化插入操作，但在此题目中，使用简单的列表和insert方法足够了。
对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。
虎哥作为一名老码农，整理了全网最全《python高级架构师资料合集》。
