LeetCode——分发糖果

Q：有N个小朋友站在一排，每个小朋友都有一个评分，你现在要按以下的规则给孩子们分糖果：每个小朋友至少要分得一颗糖果，分数高的小朋友要他比旁边得分低的小朋友分得的糖果多。你最少要分发多少颗糖果？
A：
先从左往右遍历，如果比左边大加一；再从右往左遍历，如果比右边大，选择当前值和右边值+1中大的那个。

    public static int candy(int[] ratings) {
        if (ratings.length == 0)
            return 0;
        int[] candy = new int[ratings.length];
        int sum = 0;
        Arrays.fill(candy, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1])
                candy[i] = candy[i - 1] + 1;
        }
        sum += candy[ratings.length - 1];
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1])
                candy[i] = Integer.max(candy[i], candy[i + 1] + 1);
            sum += candy[i];
        }
        return sum;
    }