#Problem

#⭐️⭐️⭐️

每个人至少有一颗糖, 相邻两个小朋友rating高的有更多的糖.

#Solution

Greedy, 左右各扫一遍

1
2
3
4
5
if (rating[i] > rating[i - 1]) {
res[i] = res[i - 1] + 1;
} else {
res[i] = 1;
}

从右往左再来一遍一样的.

#Code

#Java
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
26
27
class Solution {
public int candy(int[] ratings) {
final int n = ratings.length;
int[] candies = new int[n];
candies[0] = 1;
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
} else {
candies[i] = 1;
}
}
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
int sum = 0;
for (int candy : candies) {
sum += candy;
}
return sum;
}
}

Comments