LeetCode 135 - Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Solution 1:

两头扫瞄，第一次从左到右，第二次从右到左，这样递增和递减的关系就刚好相反。每一个递增都加一，递减就不变。

public int candy(int[] ratings) {
    int n = ratings.length;
    int[] candy = new int[n];
    Arrays.fill(candy, 1);
    for(int i=1, k=1; i<n; i++) {
        if(ratings[i] > ratings[i-1]) {
            candy[i] = ++k;
        } else {
            k = 1;
        }
    }
    for(int i=n-2, k=1; i>=0; i--) {
        if(ratings[i] > ratings[i+1]) {
            // i.e. [4,2,3,4,1], the previous candy count may be larger than ++k, we should get the larger one.
            candy[i] = Math.max(candy[i], ++k);
        } else {
            k = 1;
        }
    }
    int sum = 0;
    for(int num : candy) {
        sum += num;
    }
    return sum;
}

上面代码中的K其实可以用candy数组中的上个元素的值替代，因为只要比上一个元素值大1就行。

所以代码可以改成这个样子：

public int candy(int[] ratings) {
    int n = ratings.length;
    int[] candy = new int[n];
    Arrays.fill(candy, 1);
    for(int i=1; i<n; i++) {
        if(ratings[i] > ratings[i-1]) {
            candy[i] = candy[i-1] + 1;
        }
    }
    for(int i=n-2; i>=0; i--) {
        if(ratings[i] > ratings[i+1]) {
            // i.e. [4,2,3,4,1], the previous candy count may be larger than candy[i+1]+1, we should get the larger one.
            candy[i] = Math.max(candy[i], candy[i+1] + 1);
        }
    }
    int sum = 0;
    for(int num : candy) {
        sum += num;
    }
    return sum;
}

 

Solution 2:

网上很多文章给出了这种解法。我在leetcode上测试了下，会曝出运行超时。

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;
}