135.分发糖果 Candy

忘是亡心i 2022-12-30 08:04 137阅读 0赞

## 题目描述 ##

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：**1**.每个孩子至少分配到 1 个糖果。**2**.相邻的孩子中，评分高的孩子必须获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？

**示例 1**:

> 输入: \[1,0,2\]  
> 输出: 5  
> 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

**示例 2**:

> 输入: \[1,2,2\]  
> 输出: 4  
> 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。  
> 第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

来源：力扣（LeetCode）[链接][Link 1]

## 题解 ##

平安夜给孩子这么难的题目，孩子都哭了。这道题使用的**贪心思想**，先从左到右遍历数组找到解，再从右到左遍历数组找到解，然后取二者的最大值即为每个人得到的糖果数。

执行用时：96 ms, 在所有 Python3 提交中击败了30.58%的用户；  
内存消耗：16.7 MB, 在所有 Python3 提交中击败了11.68%的用户。

class Solution:
        def candy(self, ratings: List[int]) -> int:
            n = len(ratings)
            left = [0] * n
            right = 0
            sum = 0
            # 左遍历
            for i in range(n):
                if i > 0 and ratings[i] > ratings[i - 1]:
                    left[i] = left[i - 1] + 1
                else:
                    left[i] = 1
            # 右遍历
            for i in range(n - 1, -1, -1):
                if i < n - 1 and ratings[i] > ratings[i + 1]:
                    right += 1
                else:
                    right = 1
                sum += max(right, left[i])
            return sum

[Link 1]: https://leetcode-cn.com/problems/candy

发表评论取消回复

表情：

评论列表（有 0 条评论，137人围观）

还没有评论，来说两句吧...

相关阅读

相关 135.分发糖果 Candy

题目描述老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：1.每个孩子至少

忘是亡心i/ 2022年12月30日 08:04/ 0 赞/ 138 阅读

相关 135. Candy (Hard)

135. Candy (Hard) 题目描述一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一个孩子的评分比自己身旁的一个孩子

深碍√TFBOYSˉ_/ 2022年11月03日 01:35/ 0 赞/ 113 阅读

相关 leetcode 135. Candy | 135. 分发糖果（原创图文详解，Java）

题目 [https://leetcode.com/problems/candy/][https_leetcode.com_problems_candy] ![在这里插

小咪咪/ 2022年10月10日 12:47/ 0 赞/ 182 阅读

相关 135. 分发糖果

> 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。 > > 你需要按照以下要求，帮助老师给这些孩子分发糖果： > > 每个

叁歲伎倆/ 2022年10月05日 10:59/ 0 赞/ 123 阅读

相关 Leetcode 135. 分发糖果

题目重述老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个孩子

一时失言乱红尘/ 2022年09月13日 15:26/ 0 赞/ 131 阅读

相关 leetcode 135 分发糖果

前言题目：[135. 分发糖果][135.] 参考题解：[分发糖果-力扣官方题解][-] -------------------- 提交代码我没想出来，看

桃扇骨/ 2022年08月28日 09:55/ 0 赞/ 124 阅读

相关 leetcode 135. Candy

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

迈不过友情╰/ 2022年07月28日 09:51/ 0 赞/ 127 阅读

相关 [Leetcode][python]Candy/分发糖果

题目大意一直线上站了N个孩子，每个孩子都有一个属于自己的数字，现在按照如下规则给孩子分发糖果：每个孩子至少有一个糖果；相邻的孩子中数字比较大的那个拿的糖果也比较多。求最

左手的ㄟ右手/ 2022年06月05日 05:05/ 0 赞/ 170 阅读

相关 LeetCode 135.Candy （分发糖果）

题目描述：老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个

我不是女神ヾ/ 2022年05月08日 10:06/ 0 赞/ 151 阅读

相关 135. Candy

class Solution { public int candy(int[] ratings) { int[] candies

￡神魔★判官ぃ/ 2021年12月22日 06:53/ 0 赞/ 150 阅读