LeetCode 根据身高重建队列题解

LeetCode 根据身高重建队列题解题目描述假设有打乱顺序的一群人站成一个队列数组 people 表示队列中一些人的属性。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi前面正好有 ki 个身高大于或等于 hi 的人。示例输入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]]解题思路方法贪心思路首先按照身高从高到低排序如果身高相同则按照 ki 从小到大排序。然后按照排序后的顺序将每个人插入到结果队列的第 ki 个位置。复杂度分析时间复杂度O(n^2)。空间复杂度O(n)。代码实现def reconstruct_queue(people): people.sort(keylambda x: (-x[0], x[1])) result [] for p in people: result.insert(p[1], p) return result # 测试 def test_reconstruct_queue(): people [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]] print(reconstruct_queue(people)) # 输出[[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]] if __name__ __main__: test_reconstruct_queue()总结根据身高重建队列是贪心算法的典型应用通过排序和插入操作来重建队列。