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?
class Solution {
public:
int candy(vector<int> &ratings) {
vector<int> candy_number(ratings.size(), );
//不用迭代器，改用下标索引实现，这样代码看起来更加简洁
for(int i=; i<ratings.size(); ++i)
{
//保障当右边的rating比左边的高时，则右边分得的糖果比左边多
if( ratings[i] > ratings[i-]) //eg：输入[4 2 3 4 1],最少的分法是[2 1 2 3 1],分发9个糖果
candy_number[i] = (candy_number[i] > candy_number[i-]+) ? candy_number[i] : candy_number[i-]+;
}
for(int i=ratings.size()-; i>=; --i)
{
//保障当左边的rating比右边的高时，则左边分得的糖果比右边多
if( ratings[i] > ratings[i+])
candy_number[i] = (candy_number[i] > candy_number[i+]+) ? candy_number[i] : candy_number[i+]+;
}
int total=;
for(int i=; i!=ratings.size(); ++i)
total = total + candy_number[i];
return total;
}
};