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 1result = [1]*nums# 从左到右遍历，右边大的+1for 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)