-
Notifications
You must be signed in to change notification settings - Fork 1
/
Candy.java
37 lines (37 loc) · 1.03 KB
/
Candy.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
28
29
30
31
32
33
34
35
36
37
/**
* 135. Candy
* 贪心算法。
* 两次遍历,分别满足左规则和右规则,然后取其中较大即可。
* 参考题解 https://leetcode-cn.com/problems/candy/solution/candy-cong-zuo-zhi-you-cong-you-zhi-zuo-qu-zui-da-/
* @author LBW
*/
public class Candy {
public int candy(int[] ratings) {
int n = ratings.length;
int[] left = new int[n];
left[0] = 1;
for (int i = 0; i < n - 1; i++) {
if (ratings[i] < ratings[i + 1]) {
left[i + 1] = left[i] + 1;
}
else {
left[i + 1] = 1;
}
}
int[] right = new int[n];
right[n - 1] = 1;
for (int i = n - 1; i > 0; i--) {
if (ratings[i] < ratings[i - 1]) {
right[i - 1] = right[i] + 1;
}
else {
right[i - 1] = 1;
}
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += Math.max(left[i], right[i]);
}
return sum;
}
}