题目描述

解题思路

思路就是两个维度的判断，先判断一个维度，首先根据身高进行排序，从大到小排好序后，此时在按照频率k来进行排序，此时不用调顺序也可以保证每个前面都是大于本身的，因为已经按照身高排序好了。
本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后在按照另一个维度重新排列。
如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。
那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。
此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！
那么只需要按照k为下标重新插入队列就可以了，为什么呢？
以图中{5,2} 为例：
按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。
所以在按照身高从大到小排序后：
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性

// 局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
// 全局最优：最后都做完插入操作，整个队列满足题目队列属性
public int[][] reconstructQueue(int[][] people) {
    // 身高从大到小排（身高相同k小的站前面）
    Arrays.sort(people, (a, b) -> {
        if (a[0] == b[0]) return a[1] - b[1];
        return b[0] - a[0];
    });
    ArrayList<int[]> res = new ArrayList<>();
    // 将身高按照k进行排序
    for (int[] ints : people) {
        res.add(ints[1], ints);  // 在此列表中的指定位置插入指定的元素。
    }
    // public <T> T[] toArray(T[] a) 传入泛型
    return res.toArray(new int[res.size()][]);
}