每日一题力扣135 分糖果 中级

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/candy
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的答案：

就是列表两侧加0，然后从左往右进行一个遍历查看是否有某个i位置，它比前后都多，都多的话那么就多给它分配一颗糖，并且i+=2。但是很遗憾超时了

class Solution:
#     def candy(self, ratings: List[int]) -> int:
#         #先在列表左右两侧加0，然后遍历这个列表，如果遇见它比左右更多，那么count就加1.并且跳过它的右侧同学
#         r=[0]+ratings+[0]
#         i=1
#         count=0
#         while i < len(r)-1:
#             if r[i-1]<r[i] and r[i]>r[i+1]:
#                 i+=2
#                 count+=1
#         count+=(len(r)-2)
#         return count

别人的答案：

class Solution:
    def candy(self, ratings: List[int]) -> int:
        left = [1 for _ in range(len(ratings))]#每个人给一个
        right = left[:]
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]: left[i] = left[i - 1] + 1
        count = left[-1]#最后一个孩子的糖
        for i in range(len(ratings) - 2, -1, -1):#然后倒着过来
            if ratings[i] > ratings[i + 1]: right[i] = right[i + 1] + 1
            count += max(left[i], right[i])#得到的是每次最多的那次的糖
        return count