135. Candy - jiejackyzhang/leetcode-note GitHub Wiki

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?

解题思路为：

• From left to right, if ratings[i] increase, give one more
• From right to left, if ratings[i] increase, give one more
• Answer should be the max of two array

public class Solution {
    public int candy(int[] ratings) {
        if(ratings == null || ratings.length == 0) return 0;
        int[] candy = new int[ratings.length];
        candy[0] = 1;
        for(int i = 1; i < candy.length; i++) {
            candy[i] = (ratings[i] > ratings[i-1] ? candy[i-1]+1 : 1);
        }
        int res = candy[candy.length-1];
        for(int i = candy.length-2; i >= 0; i--) {
            if(ratings[i] > ratings[i+1]) {
                candy[i] = Math.max(candy[i], candy[i+1] + 1);
            }
            res += candy[i];
        }
        return res;
    }
}