Candy

Question:

http://www.lintcode.com/en/problem/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?

Answer:

class Solution {
public:
    /*
     * @param ratings: Children's ratings
     * @return: the minimum candies you must give
     */
    int candy(vector<int> &ratings) {
        // write your code here
        vector<int> candys(ratings.size(), 1);
        for (int i = 0; i < ratings.size() - 1; i++) {
            if (ratings[i+1] > ratings[i])
                candys[i+1] = candys[i] + 1;
        }
        for (int i = ratings.size() - 1; i > 0; i--) {
            if (ratings[i-1] > ratings[i])
                candys[i-1] = max(candys[i] + 1, candys[i-1]);
        }
        int count = 0;
        for (auto i : candys)
            count += i;
        return count;
    }
};

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️