分糖果问题

[编程题]分糖果问题

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

算法知识视频讲解

JavaScript Node

矜持的微笑

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 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)

JavaScript Node

SCUT-Criz

/**
 * 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)