题解 | #分糖果问题#

标签：贪心

解题思路参考：

https://blog.nowcoder.net/n/aff3f403aeaf43baa73e35253f71b325

class Solution:
    def candy(self , arr: List[int]) -> int:
        # 1.创建一个N个元素的数组，记录每个元素对应的糖果数，初始值为1
        candys = [1] * len(arr)
        # 2.从左往右遍历（第2个元素 -》 最后个元素）
        for i in range(1, len(arr)):
            # 如果右边元素比左边大，说明是递增关系，右边比左边元素增大1个；否则，保持1不变
            if arr[i] > arr[i - 1]:
                candys[i] = candys[i - 1] + 1
                
        i = len(arr) - 2
        # 3.从右往左遍历（倒数第2个元素 -》 第1个元素）
        while i >= 0:
            # 如果左边元素比右边大，说明是递减关系；如果左边的糖果数未比右边大，则左边比右边元素增大1个；否则，保持不变
            if arr[i] > arr[i + 1] and candys[i] <= candys[i + 1]:
                candys[i] = candys[i + 1] + 1
            i -= 1
        
        # 4.返回糖果总数
        return sum(candys)