題目:
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,這就保證了另一個方向上滿足要求
代碼:
import java.util.Arrays;
public class Solution {
public int candy(int[] ratings) {
if(ratings == null || ratings.length == 0){
return 0;
}
int n = ratings.length;
int[] candy = new int[n];
int sum=0;
Arrays.fill(candy,1);
for(int i=1;i<n;i++){
if(ratings[i]>ratings[i-1]){
candy[i] = candy[i-1]+1;
}
}
for(int i=n-1;i>=1;i--){
if(ratings[i-1]>ratings[i] && candy[i-1] <= candy[i]){
candy[i-1 ] = candy[i]+1;
}
}
for(int num:candy){
sum+=num;
}
return sum;
}
}