'''
135. 分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

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

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

 

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
'''
#  我们可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理。

# 左规则：当 ratings[i−1]<ratings[i] 时，i 号学生的糖果数量将比 i - 1 号孩子的糖果数量多。

# 右规则：当 [i + 1]ratings[i]>ratings[i+1] 时，i 号学生的糖果数量将比 i + 1 号孩子的糖果数量多。

# 我们遍历该数组两次，处理出每一个学生分别满足左规则或右规则时，最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值。

# 两次贪心：一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
# 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。
# 这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。
class Solution:
    def candy(self, ratings: list) -> int:
        n = len(ratings)
        left =[1]*n
        for i in range(n):
            if(i>0 and ratings[i]>ratings[i-1]):
                left[i]=left[i-1]+1
            # else:
            #     left[i]=1
        right = ret = 0
        for i in range(n - 1, -1, -1):
            if i < n - 1 and ratings[i] > ratings[i + 1]:
                right += 1
            else:
                right = 1
            ret += max(left[i], right)
        
        return ret
