Leetcode[135] Candy
10 Nov 2015###Task1 There are N children standing in a line. Each child is assigned a rating value.
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. What is the minimum candies you must give? ###Python
class Solution(object):
def candy(self, ratings):
"""
:type ratings: List[int]
:rtype: int
"""
N = len(ratings)
ret = [1 for i in range(N)]
for i in range(1, N):
if ratings[i] > ratings[i - 1]:
ret[i] = ret[i - 1] + 1
for i in range(N - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
ret[i] = max(ret[i], ret[i + 1] + 1)
return sum(ret)
###Java
public class Solution {
public int candy(int[] ratings) {
if (ratings == null || ratings.length == 0) {
return 0;
}
int res = 0;
int[] candies = new int[ratings.length];
candies[0] = 1;
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
} else {
candies[i] = 1;
}
}
res = candies[candies.length - 1];
for (int i = candies.length - 2; i >= 0; i--) {
int crt = 1;
if (ratings[i] > ratings[i + 1]) {
crt = candies[i + 1] + 1;
}
res += Math.max(crt, candies[i]);
candies[i] = crt;
}
return res;
}
}
###Points
- O(n)
-
Two pointers? Two pass: first pass ensures that left side conform to the rule; second pass ensures not only the right side also conform to the rule but also maintain the result from first pass. In other words:
ret[i] = max(ret[i], ret[i + 1] + 1)