首页 > 试题广场 >

分糖果问题

[编程题]分糖果问题
  • 热度指数：66859 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：

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

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

要求: 时间复杂度为 空间复杂度为

数据范围：  ，

示例1

输入

[1,1,2]

输出

4

说明

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

输入

[1,1,1]

输出

3

说明

最优分配方案是1,1,1
算法知识视频讲解
添加回答
Python3
牛客35961088号头像 牛客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)
C/C++
jjflybiubiubiu头像 jjflybiubiubiu

贪心算法
每次记录一个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)
牛超123头像 牛超123
😀🤣🤣🤣🤣🤣🤣🤣🤣🤣😍😍😍😍😘😘
发表于 2022-05-05 19:57:36 回复(0)
Java
花落梦里头像 花落梦里 
    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)
牛客180605028号头像 牛客180605028号 
 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)
C/C++
iiikant头像 iiikant 

	
	

		//把所有孩子的糖果数初始化为 1; 先从左往右遍历一遍，
	


	

		//如果右边孩子的评分比左边的高，则
	


	

		//右边孩子的糖果数更新为左边孩子的 糖果数加 1;
	


	

		//再从右往左遍历一遍，如果左边孩子的评分
	


	

		//比右边的高，且左边孩子当前的糖果数 
	


	

		//不大于右边孩子的糖果数，则左边孩子的糖果数更新为
	


	

		//右边孩子的糖果数加 1。通过这两次遍历， 分配的糖果就可以满足题目要求了。
	




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;
    }
};
遍历两遍即可求解。

发表于 2021-01-18 17:20:00 回复(1)
JavaScript Node
SCUT-Criz头像 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)
C++
Spectre_头像 Spectre_ 
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)
C++
整顿职场的外卷侠很年轻头像 整顿职场的外卷侠很年轻

  • 相邻可有两个方向，同时根据依赖方向来决定遍历顺序

    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)
Java
yxjing头像 yxjing 
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)
C++
猪奔头像 猪奔 
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)
C#
云林s头像 云林s 
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)
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)
牛客2024007号头像 牛客2024007号 
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)
Java
李克雷头像 李克雷 
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)
Java
练习时长两年半的太平湖水怪很理智头像 练习时长两年半的太平湖水怪很理智 
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)
愿offer多多的小猪猪头像 愿offer多多的小猪猪
不严谨啊，首尾相连不？

发表于 2023-10-27 15:39:26 回复(0)
Java
喜欢拱白菜的少年G了头像 喜欢拱白菜的少年G了 
public static int candy(int[] arr) {
        // write code here
        int[] temp = new int[arr.length];
        Arrays.fill(temp, 1);
        for (int t = 0; t < arr.length; t++) {
            if ((t + 1) <= arr.length - 1 && arr[t + 1] > arr[t])
                getCandy(arr, temp, t + 1);
        }
        for (int t = arr.length - 1; t >= 0; t--) {
            if ((t - 1) >= 0 && arr[t - 1] > arr[t])
                getCandy2(arr, temp, t - 1);
        }
        for (int i = 0, j = i + 1, k = i + 2; k < temp.length; i++, j++, k++) {
            if (temp[j] - temp[i] > 1 && temp[j] - temp[k] > 1) {
                if (temp[i] > temp[k]) {
                    temp[j] = temp[i] + 1;
                } else {
                    temp[j] = temp[k] + 1;
                }
            }
        }
        int ret = 0;
        for (int num : temp) {
            ret += num;
        }
        System.out.println(Arrays.toString(temp));
        return ret;
    }

    private static void getCandy(int[] arr, int[] temp, int t) {
        temp[t]++;
        if ((t + 1) <= arr.length - 1 && arr[t + 1] > arr[t])
            getCandy(arr, temp, t + 1);
    }

    private static void getCandy2(int[] arr, int[] temp, int t) {
        temp[t]++;
        if ((t - 1) >= 0 && arr[t - 1] > arr[t])
            getCandy2(arr, temp, t - 1);
    }


发表于 2023-10-09 16:40:33 回复(0)
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)
Java
倒霉的幸运儿头像 倒霉的幸运儿
分享一个空间复杂度为O(1)的算法，很简单，大家自己想也能想出来就不说思路了：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        if(arr==null||arr.length==0) return 0;
        if(arr.length==1) return 1;
        int fall=0;
        int num=1;
        int last=1;
        for(int i=1;i<arr.length;i++){
            if(arr[i]>arr[i-1]){
                if(fall>0){
                    fall=0;
                    last=1;
                }
                num+=last+1;
                last++;
            }else if(arr[i]<arr[i-1]){
                fall++;
                if(fall==last){
                    fall++;
                }
                num+=fall;
            }else{
                num++;
                fall=0;
                last=1;
            }
        }
        return num;
    }
}
发表于 2023-09-01 19:30:08 回复(0)
提交观点

问题信息

贪心
难度：
86条回答 5979浏览

热门推荐

通过挑战的用户

相关试题

分糖果问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号