❶ “leetcode”406.根据身高重建队列【贪心算法】详细图解
“leetcode”406.根据身高重建队列的贪心算法解析如下：
解题思路： 排序：首先，我们需要对给定的人数组 people 按照身高 h 从高到低进行排序。这是贪心策略的第一步，确保在插入过程中，已经插入队列中的人身高都不低于当前要插入的人。 插入：排序后，我们按照每个人的 k 值依次将每个人插入到队列中的正确位置。由于链表在插入操作上具有 O 的复杂度，因此选择链表作为数据结构来存储队列。
具体步骤：1. 排序：将 people 数组按照身高 h 降序排列，如果身高相同，则按照 k 升序排列。2. 插入：创建一个空的链表作为队列。遍历排序后的 people 数组，对于每个人 [hi, ki]，将其插入到链表的第 ki 个位置。由于链表支持 O 复杂度的插入操作，因此这一步可以高效完成。3. 输出结果：最后，将链表转换为数组形式，即为重建后的队列。
关键点： 贪心策略：优先确定身高维度，确保在插入过程中身高条件始终满足。 数据结构选择：选择链表作为存储队列的数据结构，以提高插入操作的效率。
示例： 输入：people = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] 排序后：[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]] 插入过程： 插入 [7,0]，队列变为 [[7,0]] 插入 [7,1]，队列变为 [[7,0], [7,1]] 插入 [6,1]，队列变为 [[7,0], [6,1], [7,1]] 插入 [5,0]，队列变为 [[5,0], [7,0], [6,1], [7,1]] 插入 [5,2]，队列变为 [[5,0], [7,0], [5,2], [6,1], [7,1]] 插入 [4,4]，队列变为 [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]] 输出：[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
通过上述贪心策略和数据结构的选择，我们可以高效地解决“leetcode”406.根据身高重建队列的问题。