【每日一题-LC135】分发糖果

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.

[Python3 code]

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

复杂度分析

时间复杂度 O(N) ： 遍历两遍数组即可得到结果；
空间复杂度 O(N) ： 需要借用left，right的线性额外空间。