目录
解题思路
既然是相邻,分左右遍历,求同时满足左遍历和右遍历的情况即可。与官方解法一相同,具体看注释。
解题代码
public int candy(int[] ratings){
int n = ratings.length;
//既然是相邻,分左右遍历,求同时满足左遍历和右遍历的情况即可
int[] left = new int[n];//先从左边遍历
for(int i = 0;i < n;i++){
left[i]=1;//每个孩子最少有一个糖果
}
for(int i = 0;i < n - 1;i++){
if(ratings[i + 1]>ratings[i]){//如果从左向右后一位比当前位评分高
left[i + 1]=left[i]+1;//考虑最少原则 给后一位比当前位多一个糖果
}
}
int[] right = new int[n];//再从右边遍历
for(int i = 0;i < n;i++){
right[i] = 1;//每个孩子最少有一个糖果
}
for(int i = n - 1;i > 0;i--){
if(ratings[i - 1]>ratings[i]){//如果从右向左后一位比当前位评分高
right[i - 1]=right[i]+1;//考虑最少原则 给后一位比当前位多一个糖果
}
}
int sum = 0;
for(int i = 0;i < n;i++){
sum += Math.max(left[i],right[i]);//每一位上必须同时满足左边遍历与右边遍历的情况,取交集即最大值
}
return sum;
}