135. Candy

135. Candy

Question

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

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.

Return the minimum number of candies you need to have to distribute the candies to the children.

Solution

双向遍历。
先从左至右遍历数组,如果上一个数值小于当前数值,则当前糖果等于上一个糖果数+1。
然后从右至左遍历数组,同理计算right的数值。
然后保存right与left[]里较大的数值,作为需要分配的糖果数加入到res。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public int candy(int[] ratings) {
int[] left = new int[ratings.length];
for(int i = 0; i < ratings.length; i++){
if(i > 0 && ratings[i] > ratings[i-1]){
left[i] = left[i-1] + 1;
}
else{
left[i] = 1;
}
}

int right = 0, res = 0;
for(int i = ratings.length-1; i >= 0; i--){
if(i < ratings.length-1 && ratings[i] > ratings[i+1]){
right++;
}
else{
right = 1;
}
res += Math.max(left[i], right);
}
return res;
}
}
Author

Xander

Posted on

2022-07-04

Updated on

2022-07-04

Licensed under

Comments