There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
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.
Return the minimum number of candies you need to have to distribute the candies to the children.
class Solution {
public:
int candy(vector<int>& ratings) {
int peak = 0 , valley = 0 , size = ratings.size(),candy_count = size ;
for(int i = 1 ; i< size ;){
if(ratings[i] == ratings[i-1]){ i++ ; continue;}
peak = 0 ;
valley = 0;
while( i< size && ratings[i] > ratings[i-1]){
peak++;
i++;
candy_count += peak;
}
while(i<size && ratings[i] < ratings[i-1]){
valley++;
i++;
candy_count += valley;
}
candy_count -= min(peak,valley);
}
return candy_count;
}
};
