力扣小白刷题之406题根据身高重建队列

题目描述

假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(h, k)表示，其中 h 是这个人的身高，k 是排在这个人前面且身高大于或等于 h 的人数。编写一个算法来重建这个队列。

方法

贪心

思路

对于身高相同的人，以 k 为索引来安排站位。
当身高不同时，由于个高的人 “看不见” 个矮的人，所以优先安排个高的，再安排个矮的，都是以 k 为索引位置。
递归进行：
* 将最高的人按照 k 值升序排序，然后将它们放置到输出队列中与 k 值相等的索引位置上；
* 按降序取下一个高度，同样按 k 值对该身高的人升序排序，然后逐个插入到输出队列中与 k 值相等的索引位置上。
步骤：

1. 排序
   1. 按高度降序排序
   2. 在同一高度的人中，按 k 值升序排序
2. 逐个把它们放到输出队列中，索引值是它们的 k 值
3. 返回输出队列

代码

一些问题

1. Java.List.add()
   用于在列表的指定位置插入指定元素，并将当前处于该位置的元素及其后续元素的索引加 1。
   void add(int index,E element)
   参数说明：
   index：用于指定在其中插入指定元素处的索引。
   element：用于指定要插入的元素。
2. java.List.toArray()，将List 集合转换为某种类型的数组。
   
3. 为什么是贪心？
   高个子的人可以忽略矮个子的人，即每个人的插入位置只与比自己高的人相关，所以可以想到，先按身高由高到低排序再依次按 k 插入，这样刚好可以满足贪心的无后效性。然后每一次插入时，p[1] 刚好是插入序号，这个位置是对当前的人来说最正确的决策，即局部最优。全部插入完毕则形成全局最优。