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大于前一位rating的糖果数量也增加1个。之后从右到左扫描一遍，把前一位rating比后一位rating大，若前一个的糖果数小于后一个的糖果数，显然是不对的，那么就需要重置。
对于考察左右两边与中间元素关系的题目，均可以使用左右扫描方法
1 package Candy; 2 3 import java.util.Arrays; 4 5 public class Candy { 6 public int candy(int[] ratings) { 7 int [] candy=new int[ratings.length]; 8 for(int i=0;i<candy.length;i++){ 9 candy[i]=1; 10 } 11 for(int i=1;i<candy.length;i++){ 12 if(ratings[i]>ratings[i-1]){ 13 candy[i]=candy[i-1]+1; 14 } 15 } 16 for(int i=candy.length-2;i>=0;i--){ 17 if(ratings[i]>ratings[i+1]&&candy[i]<=candy[i+1]) 18 { 19 candy[i]=candy[i+1]+1; 20 } 21 } 22 int sum=0; 23 for(int i=0;i<ratings.length;i++){ 24 sum+=candy[i]; 25 } 26 return sum; 27 } 28 }
原文：http://www.cnblogs.com/criseRabbit/p/4121195.html