根据身高重建队列

难度: Medium

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [h_i, k_i] 表示第 i 个人的身高为 h_i ，前面正好有 k_i个身高大于或等于 h_i 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [h_j, k_j] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

1 <= people.length <= 2000
0 <= h_i <= 10⁶
0 <= k_i < people.length
题目数据确保队列可以被重建

Submission

运行时间: 24 ms

内存: 16.5 MB

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key = lambda x: (-x[0], x[1]))
        que = []

        for p in people:
            que.insert(p[1], p)
        return que

Explain

这个题解的思路是先对输入的人员数组 people 进行排序，排序规则是按照身高 h 降序，如果身高相等则按照 k 值升序。排序后，从前往后遍历排序后的数组，根据每个人的 k 值，将其插入到结果数组 que 中的第 k 个位置。最后得到的 que 数组即为重建后的队列顺序。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 按照身高 h 降序，如果身高相等则按照 k 值升序排序
        people.sort(key = lambda x: (-x[0], x[1]))
        que = []

        # 遍历排序后的数组
        for p in people:
            # 根据 k 值将每个人插入到结果数组 que 中的第 k 个位置
            que.insert(p[1], p)
        
        return que

Explore

选择身高降序、k值升序作为排序规则是为了确保队列重建时，每个人插入的位置能够正确反映其k值所代表的前面有多少人比他高。首先按身高降序排序，确保我们总是先处理最高的人；这样插入时，队列前面的人都不会比当前正在插入的人高，满足了k值的定义。如果身高相同，则按k值升序排序，这保证了如果多个人身高相同，他们按照k值顺序插入，可以保持他们之间正确的相对位置。如果选择其他排序规则，比如身高升序或k值降序，将无法正确地构建队列，因为较矮的人可能会阻挡较高的人的插入，或者k值较大的人可能会过早地插入，破坏了队列的正确顺序。

如果`people`数组非常大，这种基于插入的方法效率较低。每次插入操作的复杂度是O(n)，因此整体的时间复杂度会达到O(n^2)，这对于大数据量是低效的。为了优化，可以考虑使用更高效的数据结构，如平衡二叉搜索树（BST），特别是支持顺序统计的BST，或者使用线段树或树状数组来优化插入操作。这些结构可以在O(log n)时间复杂度内完成插入和查询操作，从而将整体的时间复杂度降低到O(n log n)。这些方法需要更复杂的数据结构支持，但可以显著提高处理大型数据集的效率。

这种算法对于所有可能的输入都是稳定的，并且在正确实现了排序和插入逻辑的情况下，应始终产生正确的结果。算法的核心在于通过排序和按k值插入来确保每个人的相对位置正确。只要输入数据是有效的，即每个人的k值不会超过当前未处理的人数，这个算法就能正确地重建队列。不过，如果输入数据有误，例如k值不正确（比如负数或者超过了它前面应有的人数），这种方法可能无法正确执行。在实际应用中，应该对输入数据进行合理的预处理或验证，确保它们满足问题的预设条件。