题解 | #分糖果问题#

方法：贪心算法

将每个小孩的糖果数都初始化为1，再遍历数组根据相邻两个孩子的得分情况来更新糖果数目，这样就能得到最少的糖果数

具体做法:

• step 1：使用一个辅助数组记录每个位置的孩子分到的糖果，全部初始化为1.
• step 2：从左到右遍历数组，如果右边元素比相邻左边元素大，意味着在递增，糖果数就是前一个加1，否则保持1不变。
• step 3：从右到左遍历数组，如果左边元素比相邻右边元素大， 意味着在原数组中是递减部分，如果左边在上一轮中分到的糖果数更小，则更新为右边的糖果数+1，否则保持不变。
• step 4：将辅助数组中的元素累加求和。

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
  public:
    int candy(vector<int>& arr) {
        // 记录每个小孩的糖果数，初始化为1
        vector<int> num(arr.size(), 1);
	  	// 记录最终的糖果数
        int res = 0;
        // 先从左向右遍历
        for (int i = 1; i < arr.size(); i++) {
            // 如果右边得分大于左边，则右边糖果数是左边糖果数加1
            if (arr[i] > arr[i - 1])
                num[i] = num[i - 1] + 1;
        }

        res = num[arr.size() - 1];
        // 再从右向左遍历,
        for (int i = arr.size() - 2; i >= 0; i--) {
            // 如果左边得分大于右边且左边糖果数不大于右边时，左边糖果数是右边边糖果数加1
            if (arr[i] > arr[i + 1] && num[i] <= num[i + 1])
                num[i] = num[i + 1] + 1;
            res += num[i];
        }

        return res;
    }
};