题解 | #分糖果问题#

题目主要信息:

给定一个数组，每个元素代表孩子的得分，每个孩子至少分得一个糖果
相邻两个位置得分高的要比得分低的分得多，得分相同没有限制
求最少总共需要多少糖果数

举一反三：

学习完本题的思路你可以解决如下题目：

BM89. 合并区间

BM96. 主持人调度

方法：贪心算法（推荐使用）

知识点：贪心思想

贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。

思路：

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

具体做法:

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

图示：

alt

Java代码实现

import java.util.*;
public class Solution {
    public int candy (int[] arr) {
        int n=arr.length;
        if(n<=1)
            return n;
        int[] nums = new int[n];
        //初始化
        for(int i = 0; i < n; i++)
            nums[i] = 1;
        //从左到右遍历
        for(int i = 1; i < arr.length; i++){ 
            //如果右边在递增，每次增加一个
            if(arr[i] > arr[i - 1]) 
                nums[i] = nums[i - 1] + 1; 
        }
        //记录总糖果数
        int res = nums[arr.length - 1]; 
        //从右到左遍历
        for(int i = arr.length - 2; i >= 0; i--){ 
             //如果左边更大但是糖果数更小
            if(arr[i] > arr[i + 1] && nums[i] <= nums[i + 1])
                nums[i] = nums[i + 1] + 1; 
            //累加和
            res += nums[i]; 
        }
        return res;
    }
}

C++代码实现:

class Solution {
public:
    int candy(vector<int>& arr) {
        //记录每个位置的糖果数，初始为1
        vector<int> nums(arr.size(), 1); 
        //从左到右遍历
        for(int i = 1; i < arr.size(); i++){ 
            //如果右边在递增，每次增加一个
            if(arr[i] > arr[i - 1]) 
                nums[i] = nums[i - 1] + 1; 
        }
        //记录总糖果数
        int res = nums[arr.size() - 1]; 
        //从右到左遍历
        for(int i = arr.size() - 2; i >= 0; i--){ 
            //如果左边更大但是糖果数更小
            if(arr[i] > arr[i + 1] && nums[i] <= nums[i + 1]) 
                nums[i] = nums[i + 1] + 1; 
            //累加和
            res += nums[i]; 
        }
        return res;
    }
};

Python实现代码：

class Solution:
    def candy(self , arr: List[int]) -> int:
        #记录每个位置的糖果数，初始为1
        nums = [1] * len(arr) 
        #从左到右遍历
        for i in range(1,len(arr)) :
            #如果右边在递增，每次增加一个
            if arr[i] > arr[i - 1]: 
                nums[i] = nums[i - 1] + 1
        #记录总糖果数
        res = nums[len(arr) - 1] 
        i = len(arr) - 2
        #从右到左遍历
        while i >= 0: 
            #如果左边更大但是糖果数更小
            if arr[i] > arr[i + 1] and nums[i] <= nums[i + 1]: 
                nums[i] = nums[i + 1] + 1
            #累加和
            res += nums[i] 
            i -= 1
        return res

复杂度分析：

时间复杂度： $O (n)$ ，单独遍历两次
空间复杂度： $O (n)$ ，记录每个位置糖果数的辅助数组