leetcode135. 分发糖果

题目

思路

• 两者兼顾很容易顾此失彼，因此分别考虑两方向，初始化为全1数组
• 从前向后遍历：只要右边评分比左边大，result[i] = result[i-1] + 1
• 从后向前遍历：只要左边评分比右边大，result[i]=max(result[i+1]+1,result[i])

代码

class Solution:
    def candy(self, ratings: List[int]) -> int:
        nums = len(ratings)
        if nums==1:
            return 1
        result = [1]*nums

        # 从左到右遍历，右边大的+1
        for i in range(1, len(ratings)):
            if ratings[i]>ratings[i-1]:
                result[i] = result[i-1] + 1
        # 从右往左遍历，左边大的更多糖果
        for i in range(len(ratings)-2,-1,-1):
            if ratings[i]>ratings[i+1]:
                result[i] = max(result[i],result[i+1]+1)  # 这里取最大
        return sum(result)