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:
What is the minimum candies you must give?
解法：从左到右比较，第一个发1个，下一个比前一个rating高就+1，否则发1个。
然后从右到左，最后一个发1个，前一个比后一个rating高就+1,否则发1个。
取两次得到的值的最大值，然后累加。
1 public class Solution { 2 public int candy(int[] ratings) { 3 int[] leftCandys = new int[ratings.length]; 4 int[] rightCandys = new int[ratings.length]; 5 int[] candys = new int[ratings.length]; 6 int sum=0; 7 leftCandys[0]=1; 8 for (int i = 0; i < ratings.length-1; i++) { 9 if (ratings[i]<ratings[i+1]) { 10 leftCandys[i+1]=leftCandys[i]+1; 11 }else { 12 leftCandys[i+1]=1; 13 } 14 } 15 16 rightCandys[ratings.length-1]=1; 17 for (int i = ratings.length-1; i >0; i--) { 18 if (ratings[i]<ratings[i-1]) { 19 rightCandys[i-1]=rightCandys[i]+1; 20 }else { 21 rightCandys[i-1]=1; 22 } 23 } 24 25 for (int i = 0; i < candys.length; i++) { 26 candys[i]=Math.max(leftCandys[i], rightCandys[i]); 27 sum=sum+candys[i]; 28 } 29 return sum; 30 } 31 }
原文：http://www.cnblogs.com/birdhack/p/3954537.html