135. Candy

Ref: https://leetcode-cn.com/problems/candy/

这道题对糖果的分配规则属于局部最优，因此考虑贪心算法。由于仅需比较相邻孩子的评分大小，故考虑左规则和右规则分别正序和反序遍历数组，具体如下：

• 左规则：从左向右遍历数组，如果，则；
• 右规则：从右向左，如果，则。
  最后，遍历left和right，累加得到最终结果。算法代码如下：

class Solution:
    def candy(self, ratings: List[int]) -> int:
        l = len(ratings)
        if l == 0:
            return 0
        left = [1 for _ in range(l)]
        right = left[:]
        count = 1
        for i in range(1, l):
            if ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1
            count = left[-1]       
        for i in range(l - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right[i] = right[i + 1] + 1
            count += max(left[i], right[i])        
        return count