NC130：分糖果问题

解法1：左右各遍历一次

• 把所有孩子的糖果数初始化为 1;

• 先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的 糖果数加 1;

• 再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，
  则左边孩子的糖果数更新为右边孩子的糖果数加 1。

• 通过这两次遍历， 分配的糖果就可以满足题目要求了。

  import java.util.*;
  public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // write code here
        int[] tmp= new int[arr.length];
        Arrays.fill(tmp,1);
        int count=0;
  
        for(int i=1;i<arr.length;i++){
            if(arr[i]>arr[i-1]){
                tmp[i]=tmp[i-1]+1;
            }
        }
         for(int i=arr.length-1;i>0;i--){
            if(arr[i-1]>arr[i]){
                tmp[i-1]=Math.max(tmp[i-1],tmp[i]+1);
            }
        }
        for(int i:tmp)
            count+=i;
        return count;
    }
  }

  解法2：每次记录一个up连续上升的个数，down连续下降的个数，peak当前峰的高度

  

  import java.util.*;
  public class Solution {
    public int candy (int[] arr) {
        // write code here
        int up = 0, down = 0, peak = 1, res = 1;
        for (int i = 1; i < arr.length; i++) {
            res++;
            if (arr[i] > arr[i - 1]) {
                up++;
                res += up;
                down = 0;
                peak = up + 1;
            }
            else if (arr[i] == arr[i - 1]) {
                up = 0;
                down = 0;
                peak = 1;
            }
            else {
                up = 0;
                res += down;
                down++;
                if (down >= peak) 
                   res++;
            }
        }
        return res;
    }
  }