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?

一刷
题解：
先从左到右，和左边的相比，如果大于左边，就比左边多给一根
再从右到左，和右边的相比，如果大于右边，就取当前值和右边+1的最大值。

public class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        if(len<=1) return len;
        int[] num = new int[len];
        Arrays.fill(num, 1);
        
        for(int i=1; i<len; i++){
            if(ratings[i] > ratings[i-1]) num[i] = num[i-1]+1;
        }
        
        for(int i=len-1; i>0; i--){
            if(ratings[i-1] > ratings[i])
                num[i-1] = Math.max(num[i] + 1, num[i-1]);
        }
        
        int result = 0;
        for(int i=0; i<len; i++) result += num[i];
        
        return result;
        
    }
}

二刷
先从左到右，如果比左边的大，比左边多给一根。
然后从右到左，如果i-1比右边的数i大，则give[i]+1和give[i-1]中取较大值

public class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        int total = 0;
        int[] give = new int[len];
        Arrays.fill(give, 1);
        for(int i=1; i<len; i++){
            if(ratings[i] > ratings[i-1]) give[i] = give[i-1]+1;
        }
        
        for(int i=len-1; i>0; i--){
            if(ratings[i-1] > ratings[i])  give[i-1] = Math.max(give[i]+1, give[i-1]);
        }
        
        int res = 0;
        for(int i=0; i<len; i++){
            res += give[i];
        }
        
        return res;
    }
}