题解 | #分糖果问题#

1.贪心

思路：

要想分出最少的糖果，利用贪心思想，肯定是相邻位置没有增加的情况下，大家都分到1，相邻位置有增加的情况下，分到糖果数加1就好。什么情况下会增加糖果，相邻位置有得分差异，可能是递增可能是递减，如果是递增的话，糖果依次加1，如果是递减糖果依次减1？这不符合最小，因为减到最后一个递减的位置可能不是1，必须从1开始加才是最小，那我们可以从最后一个递减的位置往前反向加1.

具体做法:

• 把所有孩子的糖果数初始化为 1;
• 先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的 糖果数加 1;否则保持1不变
• 再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。
• 通过这两次遍历， 分配的糖果就可以满足题目要求了。

#include <numeric>
#include <vector>
class Solution {
public:
    /**
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        // write code here
        int n = arr.size();
        vector<int> res(n,1);
        //从左到右遍历
        for(int i = 1;i<n;++i)
        {
            //如果右边在递增，糖果数为左边的糖果数+1
            if(arr[i] > arr[i-1])
                res[i] = res[i-1]+1;
        }
        //从右到左遍历
        for(int i = n-2;i>=0;--i)
        {
            //如果左边更大但是糖果数更小,更新为右边的糖果数+1
            if(arr[i] > arr[i+1] && res[i] <= res[i+1] )
            {
                res[i] = res[i+1]+1;
            }
        }
        int sum = accumulate(res.begin(),res.end(),0);
        return sum;
    }
};