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比相邻的小孩高，那么他分的糖果也要比相邻小孩多，问最少需要多少糖果？
思路：先从左到右算一遍每个小孩至少要多少糖果，再从右到左，让每个小孩与右边的比一下，看看自己的糖果是否要变化。
public int candy(int[] ratings) {
if (ratings == null || ratings.length == 0) {
return 0;
}
int total = 0;
int[] nums = new int[ratings.length];
nums[0] = 1;
for (int i = 1; i < nums.length; i++) {
nums[i] = ratings[i] > ratings[i-1] ? nums[i-1] + 1 : 1;
}
for (int i = nums.length - 1; i > 0; i--) {
nums[i-1] = ratings[i-1] > ratings[i] ? Math.max(nums[i-1], nums[i] + 1) : nums[i-1];
}
for (int i = 0; i < nums.length; i++) {
total += nums[i];
}
return total;
}