题目描述

有 N 个孩子站在一排，每个孩子都有一个排名值。
你需要给这些孩子分配糖果，满足下列要求：
每个孩子至少有一块糖果；
相邻的孩子中，高排名值的糖果数要严格大于底排名值的。

求最少需要花费多少糖果。

样例

Input: [1,0,2]
Output: 5
解释: 分别分配2, 1, 2即可。

Input: [1,2,2]
Output: 4
Explanation: 分别分配1, 2, 1即可。第三个孩子分配1块可以满足以上要求。

算法1

(前向扫描+后向扫描) $O(n)$

1.初始化一个糖果列表，给每个孩子初始化1个糖果；
2.从左往右，如果当前的孩子比左边孩子优秀，他的糖果比前面的多1；
3.从右往左，如果当前孩子比右边孩子优秀，他的糖果比右边至少多1.
4.对糖果列表求和。

时间复杂度分析：o(n)

Java代码

class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies,1);
        for(int i = 1; i < ratings.length; i++) {
            if(ratings[i] > ratings[i-1]) {
                candies[i] = candies[i-1]+1;
            }
        }

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

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