老师想给孩子们分发糖果，有 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; } }
原文：https://www.cnblogs.com/WakingShaw/p/14660716.html