首页 > 试题广场 >

分糖果

[编程题]分糖果
  • 热度指数：50013 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
有N个小朋友站在一排，每个小朋友都有一个评分
你现在要按以下的规则给孩子们分糖果：
  • 每个小朋友至少要分得一颗糖果
  • 分数高的小朋友要他比旁边得分低的小朋友分得的糖果多
你最少要分发多少颗糖果？

示例1

输入

[1,2,2]

输出

4
算法知识视频讲解
开通博客
头像 offer加加加加加加一
发表于 2020-09-27 10:09:55
令dp[i]表示第i个小朋友得到的糖果，初始化dp[i] = 1如果ratings[i]>ratings[i-1]，dp[i] = max(dp[i], dp[i-1]+1)；如果ratings[i]>ratings[i+1]，dp[i] = max(dp[i], dp[i+1]+1); 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 豁达的烤冷面不讲武德
发表于 2021-09-19 10:55:07
# # 动态规划从左往右循环一次，保证比左边邻居大，从右往左保证比右边邻居大 # @param ratings int整型一维数组 # @return int整型 # class Solution: def candy(self , ratings ): # write 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 十玖八柒
发表于 2022-10-06 20:47:35
原题： 有N个小朋友站在一排，每个小朋友都有一个评分 你现在要按以下的规则给孩子们分糖果： 每个小朋友至少要分得一颗糖果 分数高的小朋友要他比旁边得分低的小朋友分得的糖果多 你最少要分发多少颗糖果？ 示例： [1,2,2] 4 [2,4,2] 4 [5,3,1] 6 注释详解： import 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 华科不平凡
发表于 2020-08-10 11:40:15
因为一个小朋友分得最少的情况与他旁边两个小朋友👬都有关🐶，因此需要从两边扫描。 细节有点折磨人，改了4次才pass，呵呵哒。 注意三个问题： 扫描的循环开始值，与终止条件，一般来说正着敦不容易出错，反着敦(如第二个循环)就容易把边界条件搞搞搞...错了 需要变更dp元素的情况是，ratings 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 FLOYD20191121155229
发表于 2024-09-23 10:41:54
class Solution { public: /** * * @param ratings int整型vector * @return int整型 */ int candy(vector<int>& ratings) 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
来自：经典编程练习-难题卷
难度：
137条回答 34594浏览

热门推荐

通过挑战的用户

查看代码

相关试题

分糖果

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号