Scan the rating array from left to right and then from right to left. In every scan just consider the rising order (l->r: r[i]>r[i-1] or r->l: r[i]>r[i+1]), assign +1 candies to the rising position.
The final candy array is the maximum (max(right[i],left[i])) in each position.
The total candies is the sum of the final candy array.
public class Solution {
public int candy(int[] ratings) {
int[] lc = new int[ratings.length];
int[] rc = new int[ratings.length];
int[] candies = new int[ratings.length];
int sum=0;
for(int i=0;i<ratings.length;i++) {
lc[i] = 1;
rc[i] = 1;
}
for(int i=1;i<ratings.length;i++) {
if(ratings[i]>ratings[i-1]) lc[i] = lc[i-1] + 1;
}
for(int i=ratings.length-2;i>=0;i--) {
if(ratings[i]>ratings[i+1]) rc[i] = rc[i+1] + 1;
}
for(int i=0;i<ratings.length;i++) {
candies[i] = Math.max(lc[i],rc[i]);
sum+=candies[i];
}
return sum;
}
}
No comments:
Post a Comment