09-13 leetcode-0135

题目

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

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.
Return the minimum number of candies you need to have to distribute the candies to the children.

题解

这题还是贪心

每个孩子最起码一颗糖果，然后遍历两次，根据规则计算即可

class Solution:
    def candy(self, ratings: list[int]) -> int:
        results = [1] * len(ratings)
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                results[i] = results[i - 1] + 1
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                results[i] = max(results[i], results[i + 1] + 1)
        return sum(results)

Comments