leetcode 根据等级分糖果

一时失言乱红尘 2021-12-16 08:11 205阅读 0赞

根据等级分糖果

N 个孩子站成一排，给每个人设定一个权重（已知）。按照如下的规则分配糖果：

(1) 每个孩子至少分得一颗糖果

(2) 权重较高的孩子，会比他的邻居获得更多的糖果。 总共最少需要多少颗糖果？

a. 编程实现

b. 分析给出算法的时间空间复杂度

Example 1:

Input: \[1,0,2\]

Output: 5

Example 2:

Input: \[1,2,2\]

Output: 4

a.

思路：设每个孩子分配到糖果的数组为candies，全部初始化为1，代表了没人至少分配到一颗糖。

先从左向右扫描数组，和前面的邻居比较，如果ratings\[i\] > ratings\[i-1\]，则candies\[i\] = candies\[i-1\] + 1。

再从右向左扫描数组，和后面的邻居比较，如果ratings\[i\] > ratings\[i+1\]，则candies\[i\]取candies\[i\]和candies\[i+1\]中的较大者。

最后对candies求和即可。

java代码如下（主函数和测试函数在Candy.java文件中）：

**public** **int** find(**int**\[\] ratings) \{

**int**\[\] candies = **new** **int**\[ratings.length\];

Arrays.*fill*(candies, 1);

**for**(**int** i = 1; i < candies.length ; i\++) \{

**if**(ratings\[i\] > ratings \[i\-1\]) \{

candies\[i\] = candies\[i\-1\] + 1;

\}

\}

**for**(**int** i = candies.length \- 2 ; i>=0 ;i\--) \{

**if**(ratings\[i\] > ratings\[i\+1\]) \{

candies\[i\] = Math.*max*(candies\[i\], candies\[i\+1\] + 1);

\}

\}

**int** sum = 0 ;

**for**(**int** s : candies) \{

sum \+= s;

\}

**return** sum;

\}

b.分析算法时间空间复杂度

分别从左向右和从右向左扫描candies数组，最后求和的时候再次扫描一遍candies数组，时间复杂度O(n)；

使用一个candies数组存储数据，空间复杂度O(n)。

发表评论取消回复

表情：

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

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

相关阅读

相关 ELO等级分制度

目录前言 ELO等级分制度前言近段重温了经典电影《社交网络》，在电影中，Facebook创始人马克·扎克伯格在和女友分手后，受到好友爱德华多对

矫情吗；*/ 2023年09月23日 15:12/ 0 赞/ 138 阅读

相关 Leetcode——贪心算法之分发糖果

[参考][Link 1] 算法思路：我们只需要简单的两次遍历即可：把所有孩子的糖果数初始化为 1；先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更

刺骨的言语ヽ痛彻心扉/ 2023年01月10日 01:21/ 0 赞/ 171 阅读

相关 Leetcode 135. 分发糖果

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

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

相关 leetcode 135 分发糖果

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

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

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

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

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

相关 LeetCode575. 分糖果

给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。示例 1

不念不忘少年蓝@/ 2022年05月23日 13:07/ 0 赞/ 190 阅读

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

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

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

相关 [LeetCode]candy分糖果

题目描述 There are N children standing in a line. Each child is assigned a rating value.

àì夳堔傛蜴生んèń/ 2022年03月17日 02:30/ 0 赞/ 248 阅读

相关 leetcode 根据等级分糖果

根据等级分糖果 N 个孩子站成一排，给每个人设定一个权重（已知）。按照如下的规则分配糖果： (1) 每个孩子至少分得一颗糖果 (2) 权重较高的孩子，会比他的邻居获得更多

一时失言乱红尘/ 2021年12月16日 08:11/ 0 赞/ 206 阅读

相关【LeetCode】 1103. 分糖果 II

<table> <tbody> <tr> <td><font>题目</font></td> </tr> </tbody> </table>

旧城等待，/ 2021年06月10日 20:38/ 0 赞/ 424 阅读