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:
1、Each child must have at least one candy.
2、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) {
int n = ratings.size();
vector<int> cans(n,1);
for(int i=1;i<n;i++)
{
if(ratings[i]>ratings[i-1])
cans[i] = cans[i-1] + 1;
}
for(int i=n-2;i>=0;i--)
{
if(ratings[i]>ratings[i+1]&&cans[i]<=cans[i+1])
cans[i] = cans[i+1] + 1;
}
int result = 0 ;
for(int i=0;i<n;i++)
{
result += cans[i];
}
return result;
}
};
