【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