[leetcode] Candy | 给小孩子分糖

Posted by: lexigrey on: October 8, 2013

In: leetcode
4 Comments

一维DP。

d[i] 是给第i个小孩最少几块糖
- rank[i] > rank[i – 1]，必须比前一个多给一块，d[i] = d[i – 1] + 1
- rank[i] == rank[i – 1]，两个排名一样，第二个就给一块就行了, d[i] = 1
- rank[i] < rank[i – 1]，比上一个排名低，应该少给一块，但是若上一个已经只给一块了，就得往前推一个一个多给。推到什么时候为止呢？若排名比下一个高，糖还一样多，就得再给；直到这个关系打破（排名一样或比下一个还低，或是糖已经满足关系）就不用再往前推了。

public int candy(int[] ratings) {
    if (ratings.length == 0)
        return 0;
    int[] d = new int[ratings.length];
        d[0] = 1;
    for (int i = 1; i < ratings.length; i++) {
        if (ratings[i] == ratings[i - 1])
            d[i] = 1;
        else if (ratings[i] > ratings[i - 1])
            d[i] = d[i - 1] + 1;
        else {// should give less candy than prev child
            d[i] = 1;
            if (d[i - 1] == 1) {
                int j = i;
                while (j > 0 && ratings[j - 1] > ratings[j] && d[j - 1] == d[j]) {
                    //only push backwards when ratings diff but candy are same
                   d[j - 1]++;
                   j--;
                }
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < ratings.length; i++) {
        sum += d[i];
    }
    return sum;
}