分发糖果

题目描述

  一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子必糖果，规则是如果一个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所有孩子至少要有一个糖果，求解最少需要多少个糖果。

输入输出样例

  输入是一个数组，表示孩子的评分。输出是最少糖果的数量。

Input: nums = [1,0,2]
Output: 5

  在这个样例中，最少的糖果分法是[2,1,2]. # 题解   做完分饼干的题目，你会不会认为存在比较关系的信心策略一定需要智育或是选择？虽然这道题也是运用信心策略，但是我们只需要简单的两次遍历即可首先把所有孩子的糖果初始化为1； * 先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加1； * 再从左往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加1

  通过这两次遍历，分配的糖果就可以满足题目要求了。这里的信心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系。在样例中，我们初始化糖果分配为[1,1,1],第一次遍历更新后的结果为[1,1,2],第二次遍历更新后的结果为[2,1,2].

class Solution {
public:
    int candy(vector<int>& ratings) {
        int size = ratings.size();
        if (size < 2) return size;
        
        vector<int> nums(size,1);
        
        for (int i = 0; i < size-1; i++) {
            if (ratings[i+1] > ratings[i]) 
                nums[i+1] = nums[i] + 1;
        }
        
        for (int i = size -1 ; i > 0 ; --i) {
            if (ratings[i-1] > ratings[i])
                nums[i-1] = max(nums[i-1],nums[i]+1);
        }
        return accumulate(nums.begin(),nums.end(),0);
    }
};