leetcode135(分发糖果：二次遍历）

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现（数组 int [ ]rating），预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

题解：二次遍历，原题中“相邻的孩子中，评分高的孩子必须获得更多的糖果”这句话可以拆成两个规则：

1. 若某个孩子比他左手边的孩子评分高，则这个孩子获得的糖果数比他左手边的孩子多
2. 若某个孩子比他右手边的孩子评分高，则这个孩子获得的糖果数比他右手边的孩子多

我们两次遍历rating数组，第一次正向遍历数组，比较每个孩子和他左手边的孩子的评分，分配糖果；第二次逆向遍历数组，比较每个孩子和他右手边的孩子的评分，分配糖果。

class Solution {
    public int candy(int[] ratings) {
       int len= ratings.length;
       int[] dp=new int[len];
       //每个孩子至少分得一个糖果
       Arrays.fill(dp,1);
       for(int i=1;i<len;i++){
            if(ratings[i]>ratings[i-1]){
                dp[i]=dp[i-1]+1;
            }
        }
        
       for(int i=len-2;i>=0;i--){
           if(ratings[i]>ratings[i+1]){
               if(i-1>=0) {
                   /**
                    * 如果这个孩子比他左手和右手边得孩子评分都高，
                    * 则获得得糖果是其左右手孩子所得糖果数的最大值+1
                    */
                   if(ratings[i]>ratings[i-1]) {
                       dp[i]=Math.max(dp[i-1],dp[i+1])+1;
                   }else{
                       dp[i]=dp[i+1]+1;
                   }
               }else{
                   dp[i]=dp[i+1]+1;
               }
           }
       }
       int sum=0;
       for(int x:dp){
           sum+=x;
       }
       return sum;
    }
}