406. 根据身高重建队列（贪心算法）

406. 根据身高重建队列（贪心算法）

• 题目
• 解题思路
• 代码

题目

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

注意：
总人数少于1100人。

解题思路

先排序再插入
1.排序规则：按照先H高度降序，再按K个数升序排序
2.遍历排序后的数组，根据K插入到K的位置上

核心思想：高个子先站好位，矮个子插入到K位置上，前面肯定有K个高个子，矮个子再插到前面也满足K的要求。如果先摆矮个子，则高个子插入的时候不能保证前面是不是有K个人，因为有可能前面的人比他矮

排序后的结果为：
[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
再一个一个插入。
[7,0]
[7,0], [7,1]
[7,0], [6,1], [7,1]
[5,0], [7,0], [6,1], [7,1]
[5,0], [7,0], [5,2], [6,1], [7,1]
[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]

代码

    class Solution {
        public int[][] reconstructQueue(int[][] people) {
            if (people == null || people.length == 0 || people[0].length == 0) {
                return new int[0][0];
            }

            Arrays.sort(people, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];//如果h相等，就按照k升序，否则h按照降序
                }
            });


            List<int[]> output = new ArrayList<>();

            for (int[] p : people) {
                output.add(p[1], p);//p[1]就是p[h][k]的k， 这句话就是把p[h][k]插入到集合中索引为K的位置
            }


            return output.toArray(new int[output.size()][]);//将List转为二维数组
        }
    }