135. Candy

题目描述：N个孩子坐在一排，每个孩子分配一个等级值，按如下要求给每个孩子分糖：

1. 每个孩子至少有一个
2. 等级高的孩子比其左右孩子多

问最少需要多少糖

分析：一个方向的比较只能满足一边的大小要求，两次遍历分别从前到后和从后到前，最后加起来。时间复杂度O(n)，空间O(n)。

代码：

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> v(n);          //记录第 i 个孩子的最少增加糖的个数
        for (int i = 1, inc = 1; i < n; i ++)       //inc是加给糖的个数，最少当然是多给1个
        {
            if (ratings[i] > ratings[i - 1])
                v[i] = max(inc ++, v[i]);         //等级每增大一个下一个 inc 就要多加一个
            else 
                inc = 1;               //出现下降则重新置1
        }
        for (int i = n - 2, inc = 1; i >= 0; i --)
        {
            if (ratings[i] > ratings[i + 1])
                v[i] = max(inc ++, v[i]);
            else 
                inc = 1;
        }
        return accumulate(v.begin(), v.end(), n);            //accumulate有三个形参：前两个指定累加的范围，第三个是累加的初值。
    }
};

第二种写法：

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        int i, result = 0;
        vector<int> count(n);      //记录每个孩子的糖数
        //每一个人至少一个糖果
        for(i = 0;i < n;i++)
            count[i] = 1;

        for(i = 1; i < n ; i++)
        {
            if(ratings[i] > ratings[i-1])
                count[i] = count[i-1] + 1;
        }
        for(i = n-2;i >= 0; i--)
        {
            if(ratings[i] > ratings[i+1] && count[i] <= count[i+1])
                count[i] = count[i+1] + 1;

        }
        //统计糖果数量
        for(i = 0;i < n;i++)
            result += count[i];
        return result;
    }
};