面试150 分发糖果

思路

联想贪心算法，遍历两次数组，一次是从左到右遍历，只比较右边孩子评分比左边打的情况。第二次从右到左遍历，只比较左边孩子评分比右边大的情况。最后求和即可

class Solution:def candy(self, ratings: List[int]) -> int:candys=[1]*len(ratings)for i in range(1,len(ratings)):if ratings[i]>ratings[i-1]:candys[i]=candys[i-1]+1##这确保了每个评分比左边高的孩子拿得比左边多。但这一轮并不能保证 “比右边高的孩子也分得更多”，所以还需要第二轮处理。       #上面是考虑左边比右边大的for i in range(len(ratings)-2,-1,-1):if ratings[i]>ratings[i+1]:candys[i]=max(candys[i],candys[i+1]+1)result=0for i in range(len(candys)):result+=candys[i]return result