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?

http://www.lintcode.com/en/problem/candy/

Solution

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> candies(ratings.size(), 1);//初始化为1
        //从左到右扫一次，rating严格增，则对应candy加1
        for (int i = 1; i < ratings.size(); ++i) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        //从右向左扫一次，如果rating严格递增而candy没有严格递增，则对应candy加1
        for (int i = ratings.size()-1; i >= 0; --i) {
            if (ratings[i - 1] > ratings[i] && candies[i - 1] <= candies[i]) {
                candies[i - 1] = candies[i] + 1;
            }
        }

        return accumulate(candies.cbegin(), candies.cend(), 0);
    }
};