0135. 分发糖果

0135. 分发糖果 #

  • 标签:贪心、数组
  • 难度:困难

题目大意 #

N 个孩子站成一排。老师会根据每个孩子的表现,给每个孩子进行评分。然后根据下面的规则给孩子们分发糖果:

  • 每个孩子至少得 1 个糖果。
  • 评分更高的孩子必须比他两侧相邻位置上的孩子分得更多的糖果。

现在给定 N 个孩子的表现分数数组 ratings,要求返回最少需要准备的糖果数目。

解题思路 #

先来看分发糖果的规则。

「每个孩子至少得 1 个糖果」:说明糖果数目至少为 N 个。

「评分更高的孩子必须比他两侧相邻位置上的孩子分得更多的糖果」:可以看做为以下两种条件:

  • ratings[i - 1] < ratings[i] 时,第 i 个孩子的糖果数量比第 i - 1 个孩子的糖果数量多;
  • ratings[i] > ratings[i + 1] 时,第 i 个孩子的糖果数量比第 i + 1 个孩子的糖果数量多。

根据以上信息,我们可以设定一个长度为 N 的数组 sweets 来表示每个孩子分得的最少糖果数,初始每个孩子分得糖果数都为 1。

然后遍历两遍数组,第一遍遍历满足当 ratings[i - 1] < ratings[i] 时,第 i 个孩子的糖果数量比第 i - 1 个孩子的糖果数量多 1 个。第二遍遍历满足当 ratings[i] > ratings[i + 1] 时,第 i 个孩子的糖果数量取「第 i + 1 个孩子的糖果数量多 1个」和「第 i + 1 个孩子目前拥有的糖果数量」中的最大值。

然后再遍历求所有孩子的糖果数量和即为答案。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def candy(self, ratings: List[int]) -> int:
        size = len(ratings)
        sweets = [1 for _ in range(size)]

        for i in range(1, size):
            if ratings[i] > ratings[i - 1]:
                sweets[i] = sweets[i - 1] + 1

        for i in range(size - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                sweets[i] = max(sweets[i], sweets[i + 1] + 1)

        res = sum(sweets)
        return res
本站总访问量  次  |  您是本站第  位访问者