Candy 412

Question

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?

Example

Given ratings = [1, 2], return 3.

Given ratings = [1, 1, 1], return 3.

Given ratings = [1, 2, 2], return 4. ([1,2,1]).

Solution

我的思路：

1) 找到所有的最低点（小于等于左边元素并且小于等于右边元素），给最低点1颗糖果

2) 然后从每个最低点开始，向左右两边上升到最高点，每上升一层多给一颗糖果，两个最低点之间的最高点取给糖果多的那个值

九章答案：

1) 先给所有点1颗糖

2) 从左往右，遇到上升区间，给右边小孩比左边小孩多一颗糖

3) 从右往左，遇到上升区间，若左边小孩的糖小于等于右边小孩的糖，则给左边小孩比右边小孩多一颗糖

代码如下：

public class Solution {
    /**
     * @param ratings Children's ratings
     * @return the minimum candies you must give
     */
    public int candy(int[] ratings) {
        // Write your code here
        if(ratings == null || ratings.length == 0){
            return 0;
        }

        if(ratings.length == 1){
            return 1;
        }

        int[] result = new int[ratings.length];
        findValley(ratings, result);
        spreadFromValley(ratings, result);

        int sum = 0;
        for(int i = 0; i < result.length; i++){
            sum += result[i];
        }

        return sum;
    }

    private void findValley(int[] ratings, int[] result){
        for(int i = 0; i < ratings.length; i++){
            if(i == 0){
                if(ratings[i] <= ratings[i + 1]){
                    result[i] = 1;
                }
                continue;
            }

            if(i == ratings.length - 1){
                if(ratings[i] <= ratings[i - 1]){
                    result[i] = 1;
                }
                continue;
            }

            if(ratings[i] <= ratings[i - 1] && ratings[i] <= ratings[i + 1]){
                result[i] = 1;
            }
        }
    }

    private void spreadFromValley(int[] ratings, int[] result){
        for(int i = 0; i < result.length; i++){
            if(result[i] != 1){
                continue;
            }

            int left = i - 1;
            while(left >= 0 && ratings[left] > ratings[left + 1]){
                int value = result[left + 1] + 1;
                if(result[left] < value){
                    result[left] = value;
                }
                left--;
            }

            int right = i + 1;
            while(right <= result.length - 1 && ratings[right] > ratings[right - 1]){
                int value = result[right - 1] + 1;
                if(result[right] < value){
                    result[right] = value;
                }
                right++;
            }
        }
    }
}

九章答案：

public class Solution {
    public int candy(int[] ratings) {
        if(ratings == null || ratings.length == 0) {
            return 0;
        }

        int[] count = new int[ratings.length];
        Arrays.fill(count, 1);
        int sum = 0;
        for(int i = 1; i < ratings.length; i++) {
            if(ratings[i] > ratings[i - 1]) {
                count[i] = count[i - 1] + 1;
            }
        }

        for(int i = ratings.length - 1; i >= 1; i--) {
            sum += count[i];
            if(ratings[i - 1] > ratings[i] && count[i - 1] <= count[i]) {  // second round has two conditions
                count[i-1] = count[i] + 1;
            }
        }
        sum += count[0];
        return sum;
    }
}