老師想給孩子們分發(fā)糖果，有 N 個孩子站成了一條直線，老師會根據(jù)每個孩子的表現(xiàn)，預(yù)先給他們評分。
你需要按照以下要求，幫助老師給這些孩子分發(fā)糖果：
每個孩子至少分配到 1 個糖果。
相鄰的孩子中，評分高的孩子必須獲得更多的糖果。
那么這樣下來，老師至少需要準(zhǔn)備多少顆糖果呢？
//分?jǐn)?shù)一樣的不用給一樣的數(shù)量，可以只給1

class Solution {
    public int candy(int[] ratings) {
        if(ratings==null||ratings.length==0){
            return 0;
        }
        int len = ratings.length;
        int[] candy = new int[len];
        candy[0]=1;
        //從左至右，右邊的比左邊的大，就可以把右邊的糖果數(shù)量設(shè)置為左邊的加1
        for(int i=1;i<len;i++){
            if(ratings[i]>ratings[i-1]){
                candy[i]=candy[i-1]+1;
            }else{
                candy[i]=1;
            }
        }
        //從右邊到左邊，左邊比右邊的大，并且原來左邊的糖果數(shù)量小于等于右邊的，就可以把左邊的糖果數(shù)量設(shè)置為右邊的加1；
        for(int i=len-2;i>=0;i--){
            if((ratings[i]>ratings[i+1])&& (candy[i]<=candy[i+1])){
                candy[i]=candy[i+1]+1;
            }
        }
        int res=0;
        for(int i=0;i<len;i++){
            res+=candy[i];
        }
        return res;
    }
}

假設(shè)有打亂順序的一群人站成一個隊(duì)列。 每個人由一個整數(shù)對(h, k)表示，其中h是這個人的身高，k是排在這個人前面且身高大于或等于h的人數(shù)。 編寫一個算法來重建這個隊(duì)列。
按照h從高到低，k從小到大排序，依次插入到list的k位置

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[]>(){
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) return o1[1] - o2[1];
                return o2[0] - o1[0];
            }
        });

        int n = people.length;
        ArrayList<int[]> tmp = new ArrayList<>();

        for(int i = 0; i < n; i++)
            tmp.add(people[i][1], people[i]);

        return tmp.toArray(new int[tmp.size()][]);
    }
}