【题目】
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，至少分到一个糖果。
从左到右、从右到左两次遍历数组
【代码】
数组赋值和循环可以改进
最初版本
class Solution {
public int candy(int[] ratings) {
int sum=0;
int []tmp=new int[ratings.length];
for(int i=0;i<ratings.length;i++){
tmp[i]=1;
}
for(int i=1;i<ratings.length;i++){
if(ratings[i]>ratings[i-1]){
tmp[i]=tmp[i-1]+1;
}
}
for(int i=ratings.length-2;i>=0;i--){
if(ratings[i]>ratings[i+1]){
tmp[i]=Math.max(tmp[i],tmp[i+1]+1);
}
}
for(int i=0;i<tmp.length;i++){
sum+=tmp[i];
}
return sum;
}
}
【改进】
数组赋值
for(int i=0;i<ratings.length;i++){
tmp[i]=1;
}
等价于
Arrays.fill(tmp, 1);