原题地址

image.png

思路

这道题用贪心来解决。
本题的核心：矮个子的人对高个子来说，是“**看不见的”**。
了解了这一点，我们就可以由易到难来分析这个题。

  1. 如果所有人的个子都一样高，那应该怎么排序呢？很简单，按照下标值排序就行了。换言之，把 [x, i] 这位同学，放到i位置就可以了。
  2. 现在个子不一样高，那应该怎么排序呢？我们别忘了，矮个子对高个子来说，是“看不见”的。比如，对 [7, 0], [7, 1] 来说，现在插入一个身高为6的同学，这位同学插入哪个位置，对身高为7的两位同学来说，都无所谓，因为身高为7的两位同学的**相对位置**不受矮个子的影响。
  3. 了解了这些，思路就明确了。我们可以按身高，先排个子最高的那些人，再排次高的那些人，以此类推。排序方法就是把 [x, i] 这位同学放到 i 这个位置。比如说 [7, 0], [7, 1] 已经排好，现在要拍 [6, 1] ，那么直接把该同学放到 1 号下标处即可，变为 [7, 0], [6, 1], [7, 1] 。这样可行是因为身高为7的两位同学的先后顺序（相对位置）不受身高为6的同学的影响。

    python代码

    1. def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
    2.  # 这里的含义是先按列表中第一个元素的负值执行排序，拍好后再按照第二个元素进行排序
    3.  # 因为默认是按照key进行升序排序，所以此代码含义就是先按第一个元素进行降序排序，再按第二个元素进行升序排序
    4.  people.sort(key=lambda x: (-x[0], x[1]))  
    5.  rel = []
    6.  for p in people:
    7.      rel.insert(p[1], p)
    8.  return rel

    时空复杂度

    时间复杂度O(N)

    排序时间复杂度O(NlogN)，而每次插入时间复杂度O(K)，共N个元素进行插入，所以总插入时间复杂度O(N)

    空间复杂度O(N)

    输出列表所需空间