分糖果问题

[编程题]分糖果问题

热度指数：66859 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：

1. 每个孩子不管得分多少，起码分到一个糖果。

2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)

给定一个数组 $arr$ 代表得分数组，请返回最少需要多少糖果。

要求: 时间复杂度为 $O(n)$ 空间复杂度为 $O(n)$

数据范围： $1 \le n \le 100000$ ， $1 \le a_i \le 1000$

示例1

输入

[1,1,2]

输出

说明

最优分配方案为1,1,2

示例2

输入

[1,1,1]

输出

说明

最优分配方案是1,1,1

算法知识视频讲解

牛客题解官

发表于 2022-04-22 13:07:54

精华题解题目主要信息: 给定一个数组，每个元素代表孩子的得分，每个孩子至少分得一个糖果相邻两个位置得分高的要比得分低的分得多，得分相同没有限制求最少总共需要多少糖果数举一反三：学习完本题的思路你可以解决如下题目： BM89. 合并区间 BM96. 主持人调度方法：贪心算法（推荐使用）知识点：展开全文

LifelongCode

发表于 2021-02-05 16:08:47

解法1：左右各遍历一次把所有孩子的糖果数初始化为 1; 先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加 1; 再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖展开全文

牛客500979850号

发表于 2021-07-26 18:30:30

题意：给定一个数组，每一个数组元素对应另外一个数组值，求另外一个数组值的总和。要求：每一个数组对应的值不小于1；任意两个相邻的数组元素，大的数组元素对应的值更大，相同无限制。方法一：贪心题目主要的难点是在于实现“任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果”，因此我们利用贪心展开全文

牛客516598323号

发表于 2020-09-17 11:25:16

由于增加是有最优化的1，而减少趋向无穷；分成两个小问题，第一步顺序遍历arr数组，如果要求递增，则ans数组下一个比当前大1.第二步逆序遍历arr数组，如果要求递增且ans数组不符合要求，则ans数组上一个比当前大1.用例通过率: 100.00% 运行时间: 987ms 占用内存: 16832KB。展开全文

认认真真coding

发表于 2022-01-30 15:51:30

分糖果问题 1、题意重述一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：每个孩子不管得分多少，起码分到一个糖果。任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制) 给定一个数组 arrarr 代表得分数组，请返回最少需要多少糖果。换句话说，就是每个孩子必展开全文

fred-coder

发表于 2022-01-02 17:00:15

贪心,根据当前孩子的左右两侧分数比较得到孩子应该得到的糖果,由于要符合两侧的要求取较大值 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # pick candy # @param arr int整型一维数组 the array # @return int整型展开全文