leetcode Question: Candy

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);
    }
};