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的最大值。
public class Solution {
public int candy(int[] ratings) {
int len = ratings.length;
if(len<=1) return len;
int[] num = new int[len];
Arrays.fill(num, 1);
for(int i=1; i<len; i++){
if(ratings[i] > ratings[i-1]) num[i] = num[i-1]+1;
}
for(int i=len-1; i>0; i--){
if(ratings[i-1] > ratings[i])
num[i-1] = Math.max(num[i] + 1, num[i-1]);
}
int result = 0;
for(int i=0; i<len; i++) result += num[i];
return result;
}
}
二刷
先从左到右，如果比左边的大，比左边多给一根。
然后从右到左，如果i-1比右边的数i大，则give[i]+1和give[i-1]中取较大值
public class Solution {
public int candy(int[] ratings) {
int len = ratings.length;
int total = 0;
int[] give = new int[len];
Arrays.fill(give, 1);
for(int i=1; i<len; i++){
if(ratings[i] > ratings[i-1]) give[i] = give[i-1]+1;
}
for(int i=len-1; i>0; i--){
if(ratings[i-1] > ratings[i]) give[i-1] = Math.max(give[i]+1, give[i-1]);
}
int res = 0;
for(int i=0; i<len; i++){
res += give[i];
}
return res;
}
}
