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?

-------------------------- thinking ------------------------------------------
It's good to at least understand the second solutions.
https://oj.leetcode.com/discuss/23835/one-pass-constant-space-java-solution
https://oj.leetcode.com/discuss/13841/easy-understand-solution-with-comments-constant-space-pass

--------------------------- codes -------------------------------------------
class Solution {
public:
    int candy(vector<int> &ratings) {
        vector<int> candys(ratings.size(), 1);
        for(int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i-1]) {
                candys[i] = candys[i-1] + 1;
            }
        }
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i+1]) {
                candys[i] = (candys[i+1] + 1) > candys[i]? candys[i+1] + 1: candys[i];
            }
        }
        int result = 0;
        for (int i = 0; i < ratings.size(); i++) {
            result += candys[i];
        }
        return result;
    }
};