LeetCode-135.分发糖果、贪心算法

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
来源：力扣（LeetCode）

解题思路

①．初始一人分一个
②．先从左到右遍历一遍，每个人只和他左边的人比较，只要分数比左边人高，分到的糖果就比左边多一个
③．然后再从右到左遍历一遍，每个人只和他右边的人比较，只有分数比右边人高，分到的糖果就比右边多一个
④．每个人的糖果数在两次遍历后取最大值，即可以满足只要分数比相邻两边高则糖果就最多

题目只要求了分数高的获得更多的糖果，反之并不成立。

代码示例

class Solution {
public:
    int candy(vector<int>& ratings) {
        int size = ratings.size();
        vector<int> result(size,1);//初始一人给一个先
        for(int i = 1;i < size;++i)
        {
            if( ratings[i] > ratings[i-1] )//右边的人分数高于左边
                result[i] = result[i-1] +1;//确保比右边人至少多一个
        }
        for(int i = size-2;i >= 0 ;--i)
        {
            if( ratings[i] > ratings[i+1] )//左边的人分数高于右边
                result[i] = max(result[i],result[i+1]+1);//确保比左边人至少多一个
        }
        return accumulate(result.begin(),result.end(),0);
    }
};