BiruLyu
6/27/2017 - 3:50 AM

## 135. Candy(1st).java

``````public class Solution {
public int candy(int[] ratings) {
int res = 0;
if (ratings == null || ratings.length < 1) return res;
int len = ratings.length;
int[] candies = new int[len];
Arrays.fill(candies, 1);
res += len;
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
res += candies[i - 1];
}
}

for (int i = ratings.length - 1; i > 0; i--) {
if (ratings[i] < ratings[i - 1] && candies[i] >= candies[i - 1]) {
int temp = candies[i - 1];
candies[i - 1] = candies[i] + 1;
res += candies[i - 1] - temp;
}
}
return res;
}
}
/*
[0]
[3,2,1]
[1,1,2,2,2,1,1]
[1,1,2,2,2,1,1,3]
[1,3,4,3,2,1] => [1,2,4,3,2,1] => 13
[2,1] => [2,1] => 3
*/``````
``````public class Solution {
public int candy(int[] ratings) {
int ans = 1, cur = 1, fall = 0;
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] < ratings[i-1]) fall++;
else {
if (fall > 0) {
ans += (1+fall)*fall/2;
if (fall+1 > cur) ans += fall+1-cur;
fall = 0;
cur = 1;
}
cur = ratings[i] == ratings[i-1] ? 1: cur+1;
ans += cur;
}
}
if (fall > 0) {
ans += (1+fall)*fall/2;
if (fall+1 > cur) ans += fall+1-cur;
}
return ans;
}
}``````