题解 | 分糖果问题

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        int[] leftMax = new int[arr.length];
        int[] rightMax = new int[arr.length];
        leftMax[0] = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i - 1]) {
                leftMax[i] = leftMax[i - 1] + 1;
            } else {
                leftMax[i] = 1;
            }
        }
        rightMax[arr.length - 1] = 1;
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                rightMax[i] = rightMax[i + 1] + 1;
            } else {
                rightMax[i] = 1;
            }
        }
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += Math.max(leftMax[i], rightMax[i]);
        }
        return sum;
    }
}

这里的规则是得分高的要比旁边的最少多一个糖果。

所以我们定义两个数组来存放最少需要多少糖果。

leftMax存放从左往右需要糖果数。

rightMax存放从右往左需要的糖果数。

先初始化

最边上的肯定是1.

以从左往右为例，跟前一个比，如果数字比前一个大，则需要比前一个多一个糖果，如果小于或者等于，直接放一个就好了。

从右往左的逻辑一样。

最后遍历数组，把每一个格子的最大加起来就是答案了。

sum += Math.max(leftMax[i], rightMax[i]);