Question:
http://www.lintcode.com/en/problem/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?
Answer:
class Solution {
public:
/*
* @param ratings: Children's ratings
* @return: the minimum candies you must give
*/
int candy(vector<int> &ratings) {
// write your code here
vector<int> candys(ratings.size(), 1);
for (int i = 0; i < ratings.size() - 1; i++) {
if (ratings[i+1] > ratings[i])
candys[i+1] = candys[i] + 1;
}
for (int i = ratings.size() - 1; i > 0; i--) {
if (ratings[i-1] > ratings[i])
candys[i-1] = max(candys[i] + 1, candys[i-1]);
}
int count = 0;
for (auto i : candys)
count += i;
return count;
}
};