我要招人

去企业版

首页 > 试题广场 >

分糖果问题

[编程题]分糖果问题

热度指数：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

算法知识视频讲解

Python 3

李潇羽

class Solution:
    def candy(self , arr: List[int]) -> int:
        # write code here
        nums = [1 for i in range(len(arr))]
        for i in range(1, len(arr)):
            if arr[i] > arr[i - 1]:
                nums[i] = nums[i - 1] + 1
        for j in range(len(arr)-1,0,-1):
            if arr[j] < arr[j - 1] and nums[j] >= nums[j - 1]:
                nums[j - 1] = nums[j] + 1
        return sum(nums)

发表于 2023-09-10 18:01:32 回复(0)

Python 3

牛客429226965号

class Solution:
    def candy(self , arr: List[int]) -> int:
        # write code here
        if len(arr) == 0:
            return 0
        k = [1] * len(arr)
        # 正向遍历一遍，右边的分数大就加一
        for i in range(1, len(arr)):
            if arr[i] > arr[i-1]:
                k[i] = k[i-1] + 1
        count = k[len(arr)-1]
        # 从右往左遍历，左边分数大于右边的更新糖果数
        for i in range(len(arr)-2, -1, -1):
            if arr[i] > arr[i+1]:
                # 取max就好
                k[i] = max(k[i], k[i+1]+1)
            count += k[i]
 
        return count

发表于 2023-08-18 15:30:11 回复(0)

Python 3

牛客659597453号

class Solution:
    def candy(self , arr: List[int]) -> int:
        l = len(arr)-1
        res =[1]* len(arr)
        for i in range(1,len(arr)):
            if arr[i]>arr[i-1]:
                res[i] = res[i-1]+1
        while l :
            if arr[l-1] > arr[l]:
                res [l-1] = max(res[l]+1,res[l-1])
            l -= 1
        return sum(res)

发表于 2022-10-05 00:07:23 回复(0)

Python 3

蓝鲸与风

class Solution:
    def candy(self , arr: List[int]) -> int:
        #记录每个位置的糖果数，初始为1
        n=len(arr)
        nums = [1] * n 
        #从左到右遍历,遍历结束之后糖果数递增
        for i in range(1,n):
            if arr[i]> arr[i-1]:
                nums[i]=nums[i-1]+1
        #从右向左遍历,右边大
        for i in range(n-2,-1,-1):#倒数第2个开始
            #得分比人家少，但是糖果数比人家多，这就不行
            if arr[i]> arr[i+1] and nums[i]<= nums[i+1]:
                nums[i]=nums[i+1]+1
        res=sum(nums)
        return res

发表于 2022-08-22 20:02:21 回复(0)

Python 3

lun__

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# pick candy
# @param arr int整型一维数组 the array
# @return int整型
        
class Solution:
    def candy(self , arr: List[int]) -> int:
        # write code here 
        candyarr = [1] * (len(arr))
        
        # 从左到右 
        for i in range(1, len(arr)): 
            if arr[i] > arr[i-1]: ## 比较 当前得分和左侧得分
                candyarr[i] = candyarr[i-1] + 1 
        
        # 从右到左 
        for j in range(len(arr)-2, -1, -1): 
            if arr[j] > arr[j+1]: ## 比较 当前得分和右侧得分 
                candyarr[j] = max(candyarr[j], candyarr[j+1]+1) 
                
        return sum(candyarr)

发表于 2022-07-17 17:42:56 回复(1)

Python 3

Vivimore

class Solution:
    def candy(self , arr: List[int]) -> int:
        nums = [1] * len(arr)
        for i in range(1, len(arr)):
            if arr[i] > arr[i-1]:
                nums[i] = nums[i-1] + 1
        res = nums[len(arr)-1]
        i = len(arr) - 2
        while i >= 0:
            if arr[i] > arr[i+1] and nums[i] <= nums[i+1]:
                nums[i] = nums[i+1] + 1
            res += nums[i]
            i -= 1
        return res

发表于 2022-05-27 16:03:06 回复(0)

Python 3

神圣之风

运行超时

运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大

class Solution:

def candy(self , arr: List[int]) -> int:
# write code here
candy=[1 for i in range(len(arr))]
left_index,right_index=0,0
left_rank,right_rank=0,0
for j in range(0,len(arr)-1):
for i in range(0,len(arr)-j):
left_index,right_index=i-1,i+1
if(left_index<0):
left_rank,left_candy=0,0
else:
left_rank,left_candy=arr[left_index],candy[left_index]
if(right_index>len(arr)-1):
right_rank,right_candy=0,0
else:
right_rank,right_candy=arr[right_index],candy[right_index]
if(arr[i]>left_rank and candy[i]<=left_candy ):
candy[i]=left_candy+1
if(arr[i]>right_rank and candy[i]<=right_candy):
candy[i]=right_candy+1
return(sum(candy))

发表于 2022-04-14 11:19:45 回复(0)

Python 3

路痴喵

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# pick candy
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def candy(self , arr: List[int]) -> int:
        # write code here
        n = len(arr)
        candy = [1 for i in range(n)]
        
        for i in range(n-1):
            if arr[i] < arr[i+1]:
                candy[i+1] = candy[i] + 1
                
        for i in range(n-1, 0, -1):
            if arr[i] < arr[i-1]:
                candy[i-1] = max(candy[i-1], candy[i] + 1)
        
        return sum(candy)

发表于 2022-03-27 20:37:21 回复(0)