Leetcode/Candy.h at master · boyxgc/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
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?
*/
class Solution {
public:
    int candy(vector<int> &ratings) {
        vector<int> candies(ratings.size(), 1);

        //go from left to right
        for(int i = 1; i < ratings.size(); ++i) {
            if(ratings[i] > ratings[i-1] && candies[i] <= candies[i-1])
                candies[i] = candies[i-1]+1;
        }
        //go from right to left
        for(int i = ratings.size()-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 < candies.size(); ++i) {
            sum += candies[i];
        }

        return sum;
    }

};