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?
从后向前判断：
1、找出从小到大排列的子序列，大小为n，分配的糖果应该是1、2、3....n
2、如果 n == 1 那么就应该是比之前子序列的开头要大，即 : 如果之前子序列中数字个数大于1，那么该位置分配2个糖果（应该之后一个位置的孩子得到了1个糖果），否则得到比后一个位置的孩子糖果多1 的糖果。
3、比较麻烦的是如果遇到相同rating的孩子：相同rating 的孩子可以得到不一样的糖果。
因此每次结束的时候需要判断当前子序列结尾的数字是否与下一个子序列开始的位置的数字相同，如果不相同，需要当前子序列结尾得到的数目大于在一个子序列开始的数目；如果一样，那么可以按照之前的顺序分配，即1、2、3、4...n
public class Solution {
public int candy(int[] ratings) {
int len = ratings.length;
int result = 0;
int pos = len-1;
int flag = 0,target = 0;
while( pos >= 0){
int size = 1;
while( pos >= 1 && ratings[pos-1] < ratings[pos] ){
size++;
pos--;
target = ratings[pos];
}
if( size > 1){
result+=(1+size)*size/2;
if(size <= flag ){
if( pos+size<len && ratings[pos+size] != ratings[pos-1+size])
result+=(flag-size+1);
}
flag = 1;
}
else {
if( pos<len-1 && ratings[pos] == ratings[pos+1]){
flag = 1;
result+=1;
}
else{
result += flag+1;
flag++;
}
}
pos--;
}
return result;
}
}