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(key=lambda 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()

总结

根据身高重建队列是贪心算法的典型应用，通过排序和插入操作来重建队列。