135. Candy
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?
Subscribe to see which companies asked this question.
class Solution { public: int candy(vector<int>& ratings) { int len = ratings.size(), res = 0, i; if(len>0) { vector<int> number(len,0); // to save the number of candies for child[0:N-1] number[0] = 1; // forward scan to calculate how many candies needed for child i to make sure it has more candies than its left neighbor if it has a higher rate, otherwise, give one candy to it for(i=1; i<len;++i) number[i] = ratings[i]>ratings[i-1]?number[i-1]+1:1; // backward scan to calculate to make sure child i has more candies than its right neighbor if it has a higher rate, pick the bigger one from forward and backward scans as the final number for child i for(i=len-2, res = number[len-1]; i>=0;--i) { if( (ratings[i]>ratings[i+1]) && number[i]<(number[i+1]+1) ) number[i] = number[i+1]+1; res += number[i]; } } return res; } };
The question requires us to make sure a child with a higher rate has more candies than its left and right neighbors. One simple solution is to do two scans: one foward scan (from 1 to N-1) to make sure child i has more candies than its left neighbor if its rate is higher than its left neighbor. After the forward scan, we can guarantee that the left neighbor relationship is correct but we have to do more to make the right neighbor relationship in order; so we do the backwarad scan (from N-2 to 0) to make child i has more candies than its right neighbor i+1 if its rate is higher than its right neighbor. In the following implementation, we need a O(N) array number to save the number of candies needed for children, so it has O(N) space complexity and we do two linear scans so the time complexity is O(N)
