题目链接

英文链接：https://leetcode.com/problems/queue-reconstruction-by-height/

中文链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height/

题目详述

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

注意：
总人数少于1100人。

示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

题目详解

贪心算法。身高高的人只会看到比他高的人，所以当身高高的人固定好了位置，前面插入多少个矮的人都不会破坏高的人的条件限制。所以应该先决定高的人的位置，再决定矮的人的位置；高的人限制条件少，矮的人限制条件多。

把数组按 h 降序、k 升序进行排序。
然后依次遍历插入，把当前元素插入到合适的位置上。

示例：

输入为：people = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]，

排序后：people = [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]。

迭代过程：

[7,0] 插入第 0 个位置，有 people = [[7,0]…]。
[7,1] 插入第 1 个位置，有 people = [[7,0], [7,1]…]。
[6,1] 插入第 1 个位置，有 people = [[7,0], [6,1], [7,1]…]。
[5,0] 插入第 0 个位置，有 people = [[5,0], [7,0], [6,1], [7,1]…]。
[5,2] 插入第 2 个位置，有 people= [[5,0], [7,0], [5,2], [6,1], [7,1]…]。
[4,4] 插入第 4 个位置，有 people= [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]。

实际上就是把把数组按 h 降序、k 升序排序后，进行类似插入排序的过程，把每个元素插入到合适的位置上。

public class LeetCode_00406 {

    public int[][] reconstructQueue(int[][] people) {
        // 按 h 降序、k 升序进行排序
        Arrays.sort(people, (o1, o2) -> o1[0] != o2[0] ? Integer.compare(o2[0], o1[0]) : Integer.compare(o1[1], o2[1]));
        for (int i = 0; i < people.length; ++i) {
            int[] p = people[i];
            // 后移一位，让出插入点
            for (int j = i; j > p[1]; --j) {
                people[j] = people[j - 1];
            }
            // 插入到合适位置
            people[p[1]] = p;
        }
        return people;
    }
}

另造一个集合用来返回。

public class LeetCode_00406 {

    public int[][] reconstructQueue(int[][] people) {
        // 按 h 降序、k 升序进行排序
        Arrays.sort(people, (o1, o2) -> o1[0] != o2[0] ? Integer.compare(o2[0], o1[0]) : Integer.compare(o1[1], o2[1]));
        List<int[]> res = new ArrayList<>(people.length);
        for (int[] p : people) {
            res.add(p[1], p);
        }
        return res.toArray(new int[res.size()][]);
    }
}