Leetcode Study Day 8

Candy

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.

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
 

Constraints:

n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104

My solution

We can use greedy approach to accomplish this question.

We initialise an array full of 1 as the candy number with the same size of ratings.

int n = ratings.size();
vector <int> candies (n,1);

The main idea is iterate the ratings array from left to right first. If a child’s rating is greater than their left neighbor’s rating, assign them one more candy than their left neighbor.

for (int i = 1; i < n; i++){
    if (ratings[i] > ratings[i-1]){
        candies[i] = candies[i-1] + 1;
    }
}

Then we iterate the array again but this time we from the right to the left. If the current child’s rating is greater than the right neighbour’s rating, and the number of candies is smaller than the number of neighbour’s candy plus one, then we update the current child’s candy number by adding one to the neighbour’s candy number.

for (int i = n - 2; i >= 0; i--){
    if (ratings[i] > ratings[i+1]){
        if (candies[i] > candies[i+1] + 1){
            continue;
        }
        else candies[i] = candies[i+1] + 1;
    }
}

Finally, we sum up the candy array and return the result.

Full code

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector <int> candies (n,1);
        for (int i = 1; i < n; i++){
            if (ratings[i] > ratings[i-1]){
                candies[i] = candies[i-1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--){
            if (ratings[i] > ratings[i+1]){
                if (candies[i] > candies[i+1] + 1){
                    continue;
                }
                else candies[i] = candies[i+1] + 1;
            }
        }
        int total = 0;
        for (int i = 0; i < n; i ++){
            total += candies[i];
        }
        return total;
    }
};