贪心六：分发糖果

题目地址： 分发糖果
题目描述： 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1: 输入: [1,0,2] 输出: 5 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2: 输入: [1,2,2] 输出: 4 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

参考代码：

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> result = vector<int>(ratings.size(),1);
        // 右边孩子比左边孩子，分高
        for (int i = 1; i<ratings.size(); i++) {
            if (ratings[i] > ratings[i-1]) {
                result[i]= result[i-1]+1;
            }
        }
        
        // 右边孩子比左边孩子，分低
        for (int i = ratings.size()-1; i>0; i--) {
            
            if (ratings[i-1] > ratings[i] ) {
                
                result[i-1] = max(result[i-1], result[i]+1);
            }
        }
        int sum = 0;
        for (int i = 0; i<result.size(); i++) {
            sum = sum + result[i];
        }
        return sum;
    }
};

参考链接： https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.md