题解 | #分糖果问题，贪心策略#

import java.util.*;


public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        if(arr == null || arr.length == 0) return 0 ;
        int[] right = new int[arr.length] ;//存每个小朋友对应的糖果数
        //从前往后遍历，寻找递增的
        for(int i = 0 ; i < arr.length ; i ++) {
            right[i] = 1 ;//先默认为 1
            if(i == 0) continue ;
            //如果是递增，那么在前一个糖果数基础上加一，这个是最少要求的糖果数，不能再小了
            if(arr[i] > arr[i-1]) {
                right[i] = right[i-1] + 1 ;
            }
        }
        //从后往前遍历，寻找递减的
        for(int j = arr.length - 1 ; j > 0 ; j--) {
            if(arr[j-1] > arr[j]) {//考虑递减的情况
                int tmp = right[j] + 1 ;//在后一个的基础上加一，得出这个位置上所需要的最基本的糖果数
                if(tmp > right[j - 1]) {//取正向，和反向求出的该位置的公共最基本糖果数，即，较大值
                    right[j - 1] = tmp ;
                }
            }
        }
        int count = 0 ;
        for(int k : right) {
            count += k ;
        }
        return count ;
    }
}