"""
135. Candy
Hard

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

    Each child must have at least one candy.
    Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.
"""


class Solution:
    def candy(self, ratings: List[int]) -> int:
        size = len(ratings)
        if size < 2:
            return size

        candies = [1] * size
        for i in range(1, size):
            if ratings[i-1] < ratings[i]:
                candies[i] = candies[i-1] +1

        #print(candies)
        for i in range(size-1, 0, -1):
            if ratings[i] < ratings[i-1]:
                # 必须使用Max,不然会降低candies[i-1]的值
                candies[i-1] = max(candies[i-1], candies[i] +1)

        #print(candies)
        return sum(candies)
