-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathLeetCode135.java
More file actions
86 lines (83 loc) · 2.69 KB
/
LeetCode135.java
File metadata and controls
86 lines (83 loc) · 2.69 KB
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
package problems;
/**
* 拆分为两个规则，分别处理。
* 左规则：当 ratings[i-1] < ratings[i] 时，i 号学生的糖果数量将比 i-1 号孩子的糖果数量多。
* 右规则：当 ratings[i] > ratings[i+1] 时，i 号学生的糖果数量将比 i+1 号孩子的糖果数量多。
* 具体地，以左规则为例：我们从左到右遍历该数组，假设当前遍历到位置 i，如果有 ratings[i - 1] < ratings[i] 那么 i 号学生的糖果数量将比 i−1 号孩子的糖果数量多，
* 我们令 left[i]=left[i−1]+1 即可，否则我们令 left[i]=1。
*
*/
public class LeetCode135 {
public int candy(int[] ratings) {
int n = ratings.length;
int[] left = new int[n];
for (int i = 0; i < n; i++) {
if (i > 0 && ratings[i] > ratings[i - 1]) {
left[i] = left[i - 1] + 1;
} else {
left[i] = 1;
}
}
int right = 0, ret = 0;
for (int i = n - 1; i >= 0; i--) {
if (i < n - 1 && ratings[i] > ratings[i + 1]) {
right++;
} else {
right = 1;
}
ret += Math.max(left[i], right);
}
return ret;
}
public int candy1(int[] ratings) {
int n = ratings.length;
int ret = 1;
int inc = 1, dec=0, pre = 1;
for (int i = 1; i < n; i++) {
if(ratings[i] >= ratings[i-1]){
dec = 0;
pre = ratings[i] == ratings[i-1] ? 1:pre+1;
ret +=pre;
inc = pre;
}else{
dec++;
if(dec == inc){
dec++;
}
ret += dec;
pre=1;
}
}
return ret;
}
}
class LeetCode135_1 {
/**
* 两次遍历
* 左规则：当 ratings[i - 1] < ratings[i] 时，i 号 糖果数量 > i - 1 号 糖果数量
* 右规则：当 ratings[i] > ratings[i + 1] 时，i 号 糖果数量 > i + 1 号 糖果数量
* @param ratings
* @return
*/
public int candy(int[] ratings) {
int n = ratings.length;
int[] left = new int[n];
for (int i = 0; i < n; i++) {
if(i > 0 && ratings[i] > ratings[i - 1]) {
left[i] = left[i - 1] + 1;
} else {
left[i] = 1;
}
}
int right = 0, ret = 0;
for (int i = n - 1; i >= 0; i--) {
if(i < n - 1 && ratings[i] > ratings[i + 1]) {
right ++;
} else {
right = 1;
}
ret += Math.max(left[i], right);
}
return ret;
}
}