[leetcode]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?

答案：

public class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
    if (len == 0)
      return 0;
    int sum = 0;
    int[] candys = new int[len];
    
    /*简单初始化各个孩子所得到的糖果数,如果比自己的前一个孩子rating值高，则等于前一个孩子的糖果数+1，否则等于1*/
    for (int i=0; i<len; ++i){
       if (i == 0){
        candys[i] = 1;
        continue;
       }
       if (ratings[i] > ratings[i-1]){
         candys[i] = candys[i-1] + 1;
       }else{
         candys[i] = 1;
       }
    }
    
    /*计算总共需要的最少糖果数*/
    int total = candys[len-1];  //先把最后一个children的糖果数加上来
    for (int i=len-2; i>=0; --i){
      //回溯调整
      if (ratings[i] > ratings[i+1] && candys[i+1]+1 > candys[i]){
        candys[i] = candys[i+1]+1;
      }
      total += candys[i];
    }
    return total;
    }
}