【题目】
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
【题意】
多个小朋友站成一排，根据他们的得分分发糖果，得分高的小朋友要比旁边得分低的小朋友得到的糖果多，每个小朋友至少得到一枚糖果，问最少要准备多少糖果？
【思路】
先从左到右扫描一遍，使得右边比左边得分高的小朋友糖果数比左边多。
再从右到左扫描一遍，使得左边比右边得分高的小朋友糖果数比右边多。
使用贪心算法。使用一个数组存储每个小孩获得的糖果。因为要保证rating大的分的的糖果比两边都高。
两次遍历ratings数组，第一次从前往后遍历，使得右边比左边得分高的孩子分得的糖果多一个（因为要最少糖果）。其他的如后面比前面小的就都初始化为1。然后从后往前遍历，如果前面比后面得分高，但是前面的糖果数却没有后面高，那么前面的糖果数就是后面的糖果数+1,保证左边比右边得分高的小朋友分得的糖果多。
class Solution {
public int candy(int[] ratings) {
if(ratings.length==1) return 1;
//使用一个数组表示每个孩子分得的糖果数
int[] helper=new int[ratings.length];
//先初始化数组，给每个孩子一个糖果（题目说至少要一个）
for(int i=0;i<ratings.length;i++) helper[i]=1;
//从左往右遍历，如果后面比前面孩子得分高，那么后面的糖果加1，使得后面得分高的孩子分得的糖果也多。
for(int i=1;i<ratings.length;i++){
if(ratings[i]>ratings[i-1]){
helper[i]=helper[i-1]+1;
}
}
//上面只保证了右边得分高时右边的糖果多，么有保证左边得分高时它的糖果也多。
//这里从后往前遍历，保证左边得分高的孩子，它的糖果也比右边多。如果左边比右边得分高，但是左边分得的糖果没有比右边多，那就给左边分糖果，是右边的加1.
for(int i=ratings.length-1;i>0;i--){
if(ratings[i-1]>ratings[i]&&helper[i-1]<=helper[i]){
helper[i-1]=helper[i]+1;
}
}
int sum=0;
for(int i=0;i<ratings.length;i++){
sum+=helper[i];
}
return sum;
}
}