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?
Solution: For each child, we look at the least number of candies he/she should get from left to right, then from right to left, denoted by L and R, respectively. Then the least number of candies he/she should get in the end is max(L, R).
Correctness: It can be seen from the following four cases.
1. For any child with local minimum rating, we can safely assign ONE candy.
2. For any child with local maximum rating, we look at the left closest child with local minimum rating, and the right closest child with local minimum rating.
3. For any child with increasing rating, we look at the left closest child with local minimum rating.
4. For any child with decreasing rating, we look at the right closest child with local minimum rating.
Note: In the following Java code, we can use one additional array instead of two. In that case, when we scan from right to left, we update the same array. Furthermore, one may be able to do this in place (i.e., without an additional array). That can be done by each time finding two consecutive local minimums with candy number ONE, and compute the number of candies in between (based on the correctness analysis).
Correctness: It can be seen from the following four cases.
1. For any child with local minimum rating, we can safely assign ONE candy.
2. For any child with local maximum rating, we look at the left closest child with local minimum rating, and the right closest child with local minimum rating.
3. For any child with increasing rating, we look at the left closest child with local minimum rating.
4. For any child with decreasing rating, we look at the right closest child with local minimum rating.
Note: In the following Java code, we can use one additional array instead of two. In that case, when we scan from right to left, we update the same array. Furthermore, one may be able to do this in place (i.e., without an additional array). That can be done by each time finding two consecutive local minimums with candy number ONE, and compute the number of candies in between (based on the correctness analysis).
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 | public class Solution { public int candy(int[] ratings) { int n = ratings.length; if (n == 0) { return 0; } int[] left = new int[n]; int[] right = new int[n]; left[0] = 1; for (int i = 1; i < n; i++) { if (ratings[i] > ratings[i-1]) { left[i] = left[i-1] + 1; } else { left[i] = 1; } } right[n-1] = 1; for (int i = n - 2; i >= 0; i--) { if (ratings[i] > ratings[i+1]) { right[i] = right[i+1] + 1; } else { right[i] = 1; } } int sum = 0; for (int i = 0; i < n; i++) { sum += Math.max(left[i], right[i]); } return sum; } } |
No comments:
Post a Comment