[Leetcode] 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?

Analysis:

思路1：

顺序遍历，如果rating递增，则candy数量加一；否则等与1（注意，这个1可能不准确，所以我们需要逆序遍历）

逆序遍历，同顺序。和顺序的candy数比较，取较大的一个数。

思路2：

找到rating的谷底ratings[i-1] <= ratings[i] <= rating[i+1]，谷底的candy数量必为1.然后设定谷底左右的candy数（分别+1）

使用两个dummy rating来处理第一个和最后一个rating的情况

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] = max(candys[i], candys[i+1] + 1);
            }
        }
        
        int total = 0;
        for(int i=0; i<candys.size(); i++)
        {
            total += candys[i];
        }
        
        return total;
    }
};