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?
Example
Given ratings =
[1, 2]
, return 3
.
Given ratings =
[1, 1, 1]
, return 3
.
Given ratings =
[1, 2, 2]
, return 4
. ([1,2,1]).class Solution { public: int candy(vector<int> &ratings) { int num = ratings.size(); if(0 == num) return 0; vector<int> candies(num, 1); for(int i=1;i<num;i++) { if(ratings[i]>ratings[i-1]) candies[i] = candies[i-1]+1; } for(int i=num-2;i>=0;i--) { if(ratings[i] > ratings[i+1] && candies[i] <= candies[i+1]) { candies[i] = candies[i+1] + 1; } } int sum = 0; for(int i=0;i<num;i++) sum += candies[i]; return sum; } };