406. 根据身高重建队列 (opens new window)

1.排序

分析：解体的关键在于应该以什么样的策略，将每个人的身高和排名填入列表当中。

设想一下总共有n个人，如果是先填入身高最矮的人，那么针对他的排名k来说(0<=k<=n-1)，他前面的k个人选存在多种方案，并不是唯一的。因此填入桶时，应该按照身高从高到低的顺序填入，从而减小后续填入元素可能的方案数，也就是说每次填入身高和排名时，应该保证当前填入的位置是唯一且确定的。具体来说填入策略如下：

• 将身高按照从高到低进行降序排序。
• 对于相同身高的元素，按照升序排列。

按照这样对数组进行预处理排序之后，可以发现当前元素的排名，就是所要填入列表的索引下标。

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                if(o1[0]!=o2[0]) return o2[0]-o1[0];
                return o1[1]-o2[1];
            }
        });
        List<int[]> list=new ArrayList<>();
        list.add(people[0]);
        for(int i=1;i<people.length;i++){
            list.add(people[i][1],people[i]);
        }
        return list.toArray(new int[list.size()][]);
    }
}