【Leetcode每日一题】135. 分发糖果（贪心）

Leetcode 每日一题

题目链接： 135. 分发糖果

难度： 困难

解题思路： 每个孩子最少一个，相邻孩子评分高的比评分低的多一个糖果。贪心从左到右和从右到左分别计算出当前孩子应得的糖果。然后取左右的最大值即可。

题解：

class Solution:
    def candy(self, ratings: List[int]) -> int:
        length = len(ratings)
        left = [1 for _ in range(length)]
        right = left[:]
        count = 0
        for i in range(1, length):
            if ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1
        for i in reversed(range(length - 1)):
            if ratings[i] > ratings[i + 1]:
                right[i] = right[i + 1] + 1
        
        for i in range(length):    
            count += max(left[i], right[i])
        return count