Description
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?
Examples
Input: [1, 2, 3, 2, 1], Output: 9
The first child must has at least one candy, so the second must has at least two since she has higher rating than left neighbor. Similarly, third child must has at least three, the fifth child must has at least one, and fourth must has at least two. The minimum candies you must give is 1 + 2 + 3 + 2 + 1 = 9.
Idea
Define the height of a child to be 1, if the child is lower than both neighbors; and the height to be 1 + maximum of all neighbors (left, right) with lower ratings.
The height is a lower bound for the number of candies a child gets. This can be shown by induction on the height.
Also, by assigning each child number of candies equal to height, we are satisfying the requirements, by definition.
So, the answer is the sum of heights.
Height can be computed by dp with memoization.
Solution
class Solution {
private:
/* Fill the height at the index */
void fillHeight(vector<int> &ratings, int height[], int index, int n) {
if (!height[index]) { // Not filled yet
if ((index == 0 || ratings[index] <= ratings[index - 1]) &&
(index == n - 1 || ratings[index] <= ratings[index + 1])) {
height[index] = 1;
} else {
if (index > 0 && ratings[index] > ratings[index - 1]) {
fillHeight(ratings, height, index - 1, n);
height[index] = max(height[index], 1 + height[index - 1]);
}
if (index < n - 1 && ratings[index] > ratings[index + 1]) {
fillHeight(ratings, height, index + 1, n);
height[index] = max(height[index], 1 + height[index + 1]);
}
}
}
}
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
int height[n] = {0};
for (int i = 0; i < n; i++) {
fillHeight(ratings, height, i, n);
}
int nCandies = 0;
for (int i = 0; i < n; i++) {
nCandies += height[i];
}
return nCandies;
}
};
Performance
28 / 28 test cases passed.
