## 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?

### Analysis:

Scan the rating array from left to right and then from right to left. In every scan just consider the rising order (l->r: r[i]>r[i-1] or r->l: r[i]>r[i+1]), assign +1 candies to the rising position.The final candy array is the maximum (max(right[i],left[i])) in each position.

The total candies is the sum of the final candy array.

The time complexity is O(n).

### Code:

class Solution { public: int getC(vector<int> &r){ vector<int> lc(r.size(),1); vector<int> rc(r.size(),1); int res=0; for (int i=1;i<lc.size();i++){ if (r[i]>r[i-1]){ lc[i]=lc[i-1]+1; } } for (int i=rc.size()-2;i>=0;i--){ if (r[i]>r[i+1]){ rc[i]=rc[i+1]+1; } } for (int i=0;i<r.size();i++){ res+=max(lc[i],rc[i]); } return res; } int candy(vector<int> &ratings) { return getC(ratings); } };

## No comments:

## Post a Comment