老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/candy
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

这道题采用贪心算法。首先假设每个孩子都只能领到一颗糖果，这样得到的肯定是最小值。然后从左往右遍历一遍，如果右边的孩子的评分比左边孩子的评分高，则把右边孩子的糖果数+1；

再从右往左遍历一遍，如果左边孩子的评分比右边孩子的评分要高，同时左边孩子得到的糖果数不大于右边孩子的糖果数的话，则把左边孩子的糖果数更新为右边孩子的糖果数+1.

代码如下：

class Solution {
    public int candy(int[] ratings) {
        int people = ratings.length;
        int[] candies = new int[people];
        for(int i = 0; i < people; i++){
            candies[i] = 1;
        }
        for(int j = 1; j < people; j++){
            if(ratings[j] > ratings[j-1]){
                candies[j] = candies[j-1] + 1;
            }
        }
        for(int k = people-1; k > 0; k--){
            if(ratings[k] < ratings[k-1]){
                candies[k-1] = (candies[k-1]>candies[k]+1)? candies[k-1] : candies[k]+1;
            }
        }
        int res = 0;
        for(int a : candies){
            res += a;
        }
        return res;
    }
}