如何根据身高及前方更高人数信息还原散乱人群的排队顺序

核心思路 #

这是典型的贪心算法应用场景，核心利用「矮个子不会影响高个子的前方更高人数计数」的特性实现排序。

具体实现步骤 #

• 第一步：对所有Person对象执行排序，排序优先级规则：
  1. 优先按height字段从高到低降序排列
  2. 身高相等的情况下，按tallerAheadCount字段从小到大升序排列
• 第二步：初始化一个空的结果列表
• 第三步：遍历排序完成的Person列表，将每一个对象插入到结果列表中索引等于其自身tallerAheadCount的位置
• 第四步：遍历完成后得到的结果列表就是原始的正确排队顺序

原理说明 #

优先安排高个子的位置，后续插入的矮个子无论放在什么位置，都不会改变已经排好的高个子前方的更高人数统计，完美匹配tallerAheadCount的定义。身高相同的人优先安排tallerAheadCount更小的，因为同身高人群不会互相计入对方的「更高人数」统计，更小的计数本来就对应更靠前的位置。

代码示例（Python） #

# 入参people为所有Person组成的列表，每个元素格式为[height, tallerAheadCount]
def reconstruct_queue(people):
    # 按规则排序：身高降序，同身高则tallerAheadCount升序
    people.sort(key=lambda x: (-x[0], x[1]))
    res = []
    for p in people:
        res.insert(p[1], p)
    return res

测试用例 #

输入：[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]，完全符合排队规则。

内容的提问来源于stack exchange，提问作者Huevo