一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
1. 每个孩子不管得分多少，起码分到一个糖果。
2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
给定一个数组 
代表得分数组，请返回最少需要多少糖果。
要求: 时间复杂度为 )
空间复杂度为
数据范围： 
，
[编程题]分糖果问题
class Solution: def candy(self , arr ): # write code here res = [1] * len(arr) for i in range(1, len(arr)): if arr[i] > arr[i-1]: res[i] = res[i-1] + 1 for i in range(len(arr)-2, -1, -1): if arr[i] > arr[i+1]: res[i] = max(res[i+1] + 1, res[i]) return sum(res)
发表于 2021-07-30 14:13:30
回复(1)
贪心算法
每次记录一个up连续上升的个数，down连续下降的个数，peak当前峰的高度。遍历一次。
O(n) time, O(1) space
int candy(vector& arr) {
int up = 0, down = 0, peak = 1, res = 1;
for (int i = 1; i < arr.size(); i++) {
res++;
if (arr[i] > arr[i - 1]) {
up++;
res += up;
down = 0;
peak = up + 1;
}
else if (arr[i] == arr[i - 1]) {
up = 0;
down = 0;
peak = 1;
}
else {
up = 0;
res += down;
down++;
if (down >= peak) res++;
}
}
return res;
}
编辑于 2020-12-25 00:41:42
回复(1)
public int candy (int[] arr) {
int n=arr.length;
int[]dp=new int[n];//记录每个孩子的糖果数目
//从左向右，若是右边得分高，那么就得到左边的糖果数+1,否则设为1
dp[0]=1;
for(int i=1;i<n;i++){
if(arr[i]>arr[i-1]) dp[i]=dp[i-1]+1;
else dp[i]=1;
}
//从右向左遍历，若是左边比右边得分高，那么糖果数右边+1
int sum=dp[n-1];
for(int i=n-2;i>=0;i--){
if(arr[i]>arr[i+1]&&(dp[i]<=dp[i+1])){
dp[i]=dp[i+1]+1;
}
sum+=dp[i];
}
return sum;
}
发表于 2021-03-28 17:01:22
回复(0)
public int candy (int[] arr) {
// write code here
int a[]=new int[arr.length];
a[0]=1;
int sum=0;
if(arr.length==1){
sum=1 ;
}else{
for(int i=0;i<arr.length-1;i++){
if(arr[i+1]>arr[i]){
a[i+1]=a[i]+1;
}else {
a[i+1]=1;
}
}
}
for(int i=0;i<a.length-1;i++){
if(arr[i+1]<arr[i]&&a[i+1]==a[i]){
a[i]=a[i]+1;
if(i>=1){i=i-2;}
else {i=0;}
}
}
for(int i=0;i<a.length;i++){
sum+=a[i];
}
return sum;
}
发表于 2021-06-22 09:48:29
回复(0)
class Solution { public: /** * pick candy * @param arr int整型vector the array * @return int整型 */ int candy(vector<int>& arr) { if(arr.size() < 2){ return arr.size(); } vector<int> res(arr.size(), 1); //向右遍历 for(int i = 1; i < arr.size(); i++){ if(arr[i] > arr[i-1]){ res[i] = res[i-1] + 1; } } for(int i = arr.size() - 1; i > 0; i--){ //向左遍历 if(arr[i] < arr[i-1]){ res[i-1] = max(res[i-1], res[i]+1); } } int _count = 0; for(int i = 0; i < res.size(); i++){ _count = res[i] + _count; } return _count; } };//把所有孩子的糖果数初始化为 1; 先从左往右遍历一遍，//如果右边孩子的评分比左边的高，则//右边孩子的糖果数更新为左边孩子的 糖果数加 1;//再从右往左遍历一遍，如果左边孩子的评分//比右边的高，且左边孩子当前的糖果数//不大于右边孩子的糖果数，则左边孩子的糖果数更新为//右边孩子的糖果数加 1。通过这两次遍历， 分配的糖果就可以满足题目要求了。
遍历两遍即可求解。
发表于 2021-01-18 17:20:00
回复(1)
/**
* pick candy
* @param arr int整型一维数组 the array
* @return int整型
*/
function candy( arr ) {
// write code here
let res = arr.length
let list = arr.map(item => 1)
for(let i = 1; i < arr.length; i++){
if(arr[i] > arr[i - 1]){
res += list[i - 1]
list[i] += list[i - 1]
}
}
for(let i = arr.length - 1; i > 0; i--){
if(arr[i - 1] > arr[i]){
let add = list[i - 1] > list[i] ? 0 : list[i] - list[i - 1] + 1
res += add
list[i - 1] += add
}
}
return res
}
module.exports = {
candy : candy
};
发表于 2023-01-06 17:42:06
回复(0)
class Solution {
public:
/**
* pick candy
* @param arr int整型vector the array
* @return int整型
*/
int candy(vector<int>& arr) {
// 时间复杂度O(N)，空间复杂度O(N)
vector<int> tmp(arr.size(), 1);
for (int i = 1; i < arr.size(); ++i) {
if (arr[i] > arr[i - 1]) tmp[i] = tmp[i - 1] + 1;
}
for (int i = arr.size() - 2; i >= 0; --i) {
if (arr[i] > arr[i + 1] && tmp[i] <= tmp[i + 1]) tmp[i] = tmp[i + 1] + 1;
}
int res = 0;
for (int i = 0; i < tmp.size(); ++i) res += tmp[i];
return res;
}
};
发表于 2022-10-17 15:03:57
回复(0)
相邻可有两个方向，同时根据依赖方向来决定遍历顺序
class Solution { public: /** * pick candy * @param arr int整型vector the array * @return int整型 */ int candy(vector<int>& arr) { // write code here // base case if(arr.size() <= 1) return arr.size(); // 初始 每个人一颗 vector<int> nums(arr.size(), 1); //比左边 1->4->2->7->9 依赖的是左边 需从左往右遍历 for (int i = 1; i < arr.size(); i++) { // 该方向相邻且得分较多但糖果不多 if(arr[i - 1] < arr[i] && nums[i - 1] >= nums[i]){ nums[i] = nums[i - 1] + 1; } } // 比右边 1<-4<-2<-7<-9 从右往左遍历 依赖的是右边 for(int i = arr.size() - 2; i >= 0; i--){ if(arr[i + 1] < arr[i] && nums[i + 1] >= nums[i]){ nums[i] = nums[i + 1] + 1; } } int total = 0; for(int i = 0; i < nums.size(); i++){ total += nums[i]; } return total; } };
发表于 2023-01-20 17:48:20
回复(0)
import java.util.*;
public class Solution {
/**
* pick candy
* @param arr int整型一维数组 the array
* @return int整型
*/
public int candy (int[] arr) {
// write code here
int[] left=new int[arr.length];
int[] right=new int[arr.length];
int candy=0;
left[0]=1;
right[arr.length-1]=1;
for(int i=1;i<=arr.length-1;i++){
if(arr[i]>arr[i-1]){
left[i]=left[i-1]+1;
}else{
left[i]=1;
}
}
for(int i=arr.length-2;i>=0;i--){
if(arr[i]>arr[i+1]){
right[i]=right[i+1]+1;
}else{
right[i]=1;
}
}
for(int i=0;i<=arr.length-1;i++){
candy=candy+Math.max(left[i],right[i]);
}
return candy;
}
}
发表于 2022-08-24 20:36:12
回复(0)
class Solution {
public:
/**
* pick candy
* @param arr int整型vector the array
* @return int整型
*/
int candy(vector<int>& arr) {
// write code here
const int n = arr.size();
vector<int> increment(n);
for(int i = 1,inc = 1; i < arr.size(); i++){
if(arr[i] > arr[i - 1]) increment[i] = max(inc++,increment[i]);
else inc = 1;
}
for(int i = arr.size() - 2,inc = 1; i >= 0; i--){
if(arr[i] > arr[i + 1]) increment[i] = max(inc++,increment[i]);
else inc = 1;
}
int sum = 0;
for(int i = 0; i < increment.size(); i++){
sum += increment[i];
}
sum += n;
return sum;
}
}; 保安保护不了任何人
发表于 2021-09-01 17:28:24
回复(2)
简称相邻分数不同的糖果不同且分数大的糖果更多，且均不为0，所以可以创建一个数组存储糖果数，然后从左到右再从右到左遍历（条件：递增/反向递增的人要比前一个遍历到的人多一）确认相邻分数不同的分数高多过分数低的，糖果数组初始值均为1两次遍历完的总数就是最优解
int candy(vector<int>& arr) {
// write code here
vector<int> v(arr.size(),1);
for (int i=1; i<arr.size(); i++) {
if (arr[i]>arr[i-1]) {
v[i]=v[i-1]+1;
}
}
int res=v[arr.size()-1];
for (int i=arr.size()-2; i>=0; i--) {
if (arr[i]>arr[i+1]&&v[i]<=v[i+1] ){
v[i]=v[i+1]+1;
}
res+=v[i];
}
return res;
}
发表于 2025-10-14 22:55:42
回复(0)
class Solution:
def candy(self , arr: List[int]) -> int:
n = len(arr)
if not n:
return 0
candy = [1]*n
for i in range(1, n):
if arr[i]>arr[i-1]:
candy[i] = candy[i-1]+1
for i in range(n-2, -1, -1):
if arr[i]>arr[i+1]:
candy[i] = max(candy[i+1]+1,candy[i])
return sum(candy)
发表于 2025-03-14 22:16:43
回复(0)
using System;
using System.Collections.Generic;
class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* pick candy
* @param arr int整型一维数组 the array
* @return int整型
*/
public int candy (List<int> arr) {
int cur = 0;
int curc = 1;
int pre = 1;
int res = 1;
for(int i = 1; i < arr.Count; i++){
if(arr[i] > arr[i-1]){
res += pre + 1;
pre++;
cur = i;
curc = pre;
}
else if(arr[i] == arr[i - 1]){
cur = i;
res++;
pre = 1;
curc = pre;
}
else{
res += i - cur;
if(i - cur >= curc) res++;
pre = 1;
}
//Console.WriteLine(res);
}
return res;
}
}
编辑于 2024-01-29 19:39:37
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* pick candy
* @param arr int整型一维数组 the array
* @return int整型
*/
function candy( arr ) {
// write code here
let res=arr.map(v=>1)
for(let i=1;i<arr.length;i++){ //从一开始比较
if(arr[i]>arr[i-1]){
res[i]=res[i-1]+1
}
}
for(let i=arr.length-2;i>=0;i--){
if(arr[i]>arr[i+1]){
if(res[i]>res[i+1])continue
res[i]=Math.max(res[i],res[i+1])+1
}
}
return res.reduce((p,c)=>p+c,0)
}
module.exports = {
candy : candy
};
发表于 2024-01-29 10:31:55
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* pick candy
* @param arr int整型一维数组 the array
* @return int整型
*/
public int candy (int[] arr) {
// write code here
int n = arr.length;
int[] count = new int[n];
Arrays.fill(count, 1);
for(int i = 1; i < n; i++) {
if(arr[i] > arr[i - 1]) count[i] = count[i - 1] + 1;
}
for(int i = n - 2; i >= 0; i--) {
if(arr[i] > arr[i + 1]) count[i] = Math.max(count[i + 1] + 1, count[i]);
}
int res = 0;
for(int i = 0; i < n; i++) {
res += count[i];
}
return res;
}
}
编辑于 2024-01-18 15:53:17
回复(0)
public class Solution {
/**
* 给定一个数组 arrarr 代表得分数组，请返回最少需要多少糖果。
*
* pick candy
* @param arr int整型一维数组 the array
* @return int整型
*/
public int candy (int[] arr) {
int candy[] = new int[arr.length];
for (int i = 0; i < candy.length; i++) {
candy[i] = 1;
}
for (int i = 1; i < arr.length; i++) {
if (arr[i] > arr[i - 1]) {
candy[i] = candy[i - 1] + 1;
}
}
int count = 0 ;
for (int i = arr.length - 1; i > 0; i--) {
if (arr[i - 1] > arr[i] && candy[i - 1] <= candy[i]) {
candy[i - 1] = candy[i] + 1;
}
count += candy[i];
}
return count += candy[0];
}
}
发表于 2023-11-09 18:26:03
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* pick candy
* @param arr int整型一维数组 the array
* @return int整型
*/
// 参考代码随想录
public int candy (int[] arr) {
// write code here
int len = arr.length;
int res = 0;
int[] preMin = new int[len];
int[] sufMin = new int[len];
Arrays.fill(preMin, 1);
Arrays.fill(sufMin, 1);
for (int i = 1; i < len; i++) if (arr[i] > arr[i - 1]) preMin[i] = preMin[i-1] + 1;
for (int i = len - 2; i >= 0; i--) if (arr[i] > arr[i + 1]) sufMin[i] = sufMin[i+1] + 1;
for (int i = 0; i < len; i++) res += Math.max(preMin[i], sufMin[i]);
return res;
}
}
发表于 2023-11-09 14:49:24
回复(0)
问题信息
难度：
89条回答
683收藏
7560浏览
通过挑战的用户
查看代码-
2023-03-13 22:26:34 -
2023-02-18 17:25:08
-
2023-01-07 16:43:26 -
2022-11-14 23:16:30 -
2022-10-31 10:54:27
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
