135. Candy

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

先填充数组，然后从左边先遍历一遍，如果右边的数字大于左边的数字，右边的数字+1；然后从右边再进行第二次遍历，如果左边的数字大于右边的，那么就取这两个里面的最大值。如数组{1,2,3,1,2,3}中间3,1在比较的时候就是取candy[i]的值；如递减数组{2,1}是取candy[i + 1] + 1作为最大值。

    public int candy(int[] ratings) {
        int length = ratings.length;
        int[] candy = new int[length];
        Arrays.fill(candy, 1);

        for (int i = 1; i < length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            }
        }

        for (int i = length - 2; i >= 0; i--) {
            // if (ratings[i] > ratings[i + 1] && candy[i] <= candy[i + 1]) {
            //     candy[i] = candy[i + 1] + 1;
            // }
            if (ratings[i] > ratings[i + 1]) {
                candy[i] = Math.max(candy[i], candy[i + 1] + 1);
            }
        }

        int sum = 0;
        for (int n : candy) {
            sum += n;
        }
        return sum;
    }