分糖果问题

[编程题]分糖果问题

热度指数：66858 时间限制：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

算法知识视频讲解

Python3

牛客781599455号

 n=len(arr)
        if n==0:
            return 0
        if n==1:
            return 1
        if n>1:
            back=[1 for i in arr]
            for i in range(n-1):
                a=arr[i]
                b=arr[i+1]
                if a<b:
                    back[i+1]=back[i]+1
            for i in range(1,n):
                a=arr[-i]
                b=arr[-i-1]
                if a<b:
                    if back[-i-1]<back[-i]+1:
                        back[-i-1]=back[-i]+1
            return sum(back)

发表于 2022-11-26 16:18:31 回复(0)

Python3

JianYue

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

发表于 2022-09-28 23:35:52 回复(0)

Python3

牛客35961088号

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)