1、算法思路

把所有孩子的糖果数初始化为 1；先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加 1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。通过这两次遍历，分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系。

比如对于样例[1, 1, 2]。从左到右遍历一遍糖果数组为[1,1,2]。从右往左遍历一遍糖果数组为[1,1,2]。故返回总和4。

2、代码实现

class Solution {
public:
    /**
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        if(arr.size() == 0) return 0;
        vector<int> res(arr.size(), 1);
        //从左往右遍历
        for(int i = 0; i < arr.size() - 1; ++i)
        {
        	if(arr[i + 1] > arr[i]) res[i + 1] = res[i] + 1;
        }
        //从右往左遍历
        for(int i = arr.size() - 1; i > 0; i--)
        {
        	if(arr[i -1] > arr[i] && res[i - 1] <= res[i]) res[i - 1] = res[i] + 1;
        }
        //返回糖果数组和
        int sum = 0;
        for(auto i : res) sum += i;
        return sum; 
    }
};