题解 | #分糖果问题#

import java.util.*;


public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
     // 贪心：局部最优为最优
    public int candy (int[] arr) {
        // 首先给每人一个
        int n = arr.length;
        int[] num = new int[n];
        for(int i=0;i<n;i++){
            num[i] = 1;
        }

        // 首先从左往右遍历，因为默认为1，所以左边的数不会大于右边的数，我们做判断然后不断更新数据
        for(int i=1;i<n;i++){
            if(arr[i] > arr[i-1]){
                num[i] = num[i-1] + 1;
            }
        }

        // 记录res返回结果，就是总糖果数(先统计上最后一个，然后从后往前遍历依次获得)
        int res = num[n-1];

        // 然后我们还需要从右往左遍历，因为可能出现左侧的值比右侧大，但是糖果数没有右侧多的情况
        for(int i=n-2;i>=0;i--){
            if(arr[i] > arr[i+1] && num[i] <= num[i+1]){
                num[i] = num[i+1] + 1;
            }
            res += num[i];
        }

        return res;
    }
}