首页 > 试题广场 >

分糖果问题

[编程题]分糖果问题

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

算法知识视频讲解

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)

Java

喜欢拱白菜的少年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)

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)

Java

做则必成的勇气和信心

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // 左遍历一次，再右遍历一次
        if(arr.length<=1) return 1;
        int[] nums=new int[arr.length];//辅助数组，初始化为1
        for(int i=0;i<nums.length;i++){
            nums[i]=1;
        }
        //左遍历   i-1,i
        for(int i=1;i<arr.length;i++){//i从1开始
            if(arr[i]>arr[i-1]){   //如果原数组递增，那就给num[i]糖果+1
                nums[i]=nums[i-1]+1;
            }
        }
        int ans=nums[arr.length-1];
        //右遍历   i,i+1
        for(int i=arr.length-2;i>=0;i--){
            if(arr[i]>arr[i+1]&&nums[i]<=nums[i+1]){
                nums[i]=nums[i+1]+1;
            }
            ans=ans+nums[i];//ans原来是个空数组   使用了两次辅助数组nums[i]
        }
        return ans;
    }

发表于 2023-07-21 17:07:19 回复(0)

Java

牛客688892093号

import java.util.*;


public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // write code here
        int[] scores = new int[arr.length];
        int cd = 0;
        for (int i = 0; i < arr.length ; i++) {
            scores[i] = 1;
        }
       
                for (int i = arr.length - 1 ; i > 0; i--) {
            if (arr[i] < arr[i - 1]) {
                scores[i - 1] = scores[i] + 1;
            }
           

        }
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] < arr[i + 1] && scores[i+1] <= scores[i]) {
                scores[i + 1] = scores[i] + 1;
            }
           

        }

        for (int i = 0; i < arr.length; i++) {
            cd += scores[i];
            System.out.println(scores[i]);
        }
        return cd;
    }
}

发表于 2023-02-24 21:08:35 回复(0)

Java

wpcAlex

import java.util.*;


public class Solution {
    public int candy (int[] arr) {
        // write code here
        int n = arr.length;
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 1; i < n; i++) {
            //左侧单调递增区间
            if (arr[i] > arr[i - 1]) left[i] = left[i - 1] + 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            //右侧单调递减区间
            if (arr[i] > arr[i + 1]) right[i] = right[i + 1] + 1;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += Math.max(left[i], right[i]) + 1;
        }
        return ans;
    }
}

发表于 2023-01-28 22:33:27 回复(0)

Java

不卷了，就测开了

一开始还以为，相同得分的同学糖果相同。QAQ。后来发现不需要，想要实现相同得分的同学相同糖果把注释的两句打开。

import java.util.*;


public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // write code here
        int[] res = new int[arr.length];
        for(int i=0;i<arr.length;i++) res[i] = 1;
        for(int i=1;i<arr.length;i++){
            // if(arr[i] - arr[i-1]==0) res[i] = res[i-1];
            if(arr[i] - arr[i-1]>0) res[i] = res[i-1] + 1;
        }
        for(int i=arr.length-2;i>=0;i--){
            int temp = 0;
            // if(arr[i] - arr[i+1]==0) temp = res[i+1];
            if(arr[i] - arr[i+1]>0) temp = res[i+1] + 1;
            res[i] = Math.max(res[i],temp);
        }
        int sum = 0;
        for(int x:res) sum+=x;
        return sum;
    }
}

发表于 2022-10-01 22:05:28 回复(0)

Java

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)

Java

牛客用户007

轻轻的我来了

import java.util.*;


public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // write code here
        int[] dp = new int[arr.length];
        Arrays.fill(dp, 1);
        int res = 0;

        for (int i = 1; i < arr.length; i ++) {
            if (arr[i] > arr[i - 1]) dp[i] = dp[i - 1] + 1;
        }

        res = dp[arr.length - 1];
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1] && dp[i] <= dp[i + 1]) dp[i] = dp[i + 1] + 1;
            res += dp[i];
        }

        return res;
    }
}

发表于 2022-08-12 20:27:37 回复(0)

Java

卷死只求一个offer

题解: 要想分出最少的糖果，利用贪心思想，肯定是相邻位置没有增加的情况下，大家都分到1，相邻位置有增加的情况下，分到糖果数加1就好。
什么情况下会增加糖果，相邻位置有得分差异，可能是递增可能是递减，如果是递增的话，糖果依次加1，如果是递减糖果依次减1？
最后不符合最小，原因是序列中的两个任意两个元素之间必然是递增，递减，相等等三种情况，不管多长的序列都可以细分成任意两个元素的子问题
想象序列前半部分递增，后半部分递减，如果后半部分比前半部分短，最后减完是不是最后一个元素是不是大于1，所以不能得到最小值
如果是多个递增递减的序列的组合形成的序列，那么其中任意两个不等长子序列都会产生这个情况，所以诞生了下面的思路： 1.先从左到右，大于的就+1，小于的不管，然后从后向前遍历，前面的大于后面的就+1，假设序列只有递增递减两部分，如1232或者12321或者2321 12321肯定直接适用，前者因为3处于返回的时候的递增，所以应该更新为1个糖果+1=2，但是这样就把当时原来递增的数量给破坏了，所以由于前后子序列的不确定性
我们直接取max（原来的递增时数量，递减返回时的后置元素+1），谁大取谁，因为这样一定能满足大于两边的情况
import java.util.*;
public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        int length = arr.length;
        int count = 0;
        int num[] = new int[length];
        Arrays.fill(num,1);
        for(int i=1;i<length;i++){
            if(arr[i]>arr[i-1]){
                num[i] = num[i-1]+1;
            }
        }
        for(int i = length-1;i>0;i--){
            if(arr[i]<arr[i-1]){
                num[i-1] = Math.max(num[i-1],num[i]+1);
            }
        }
        for(int i :num){
            count+=i;
        }
        return count;

    }
}

发表于 2022-08-11 16:08:49 回复(0)

Java

FARO_Z

public class Solution {

    public int candy (int[] arr) {
        if (arr==null || arr.length==0) return 0;
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            ++res[i];
            if (i>0 && arr[i]>arr[i-1]) {
                res[i] = res[i-1]+1;
            }
        }
        int sum = 0;
        for (int i = arr.length-1; i >=0 ; i--) {
            if (i<arr.length-1 && arr[i]>arr[i+1] && res[i]<=res[i+1]) {
                res[i] = res[i+1]+1;
            }
            sum = sum + res[i];
        }
        return sum;
    }
}

发表于 2022-07-07 16:09:19 回复(1)

Java

月下独酌&wxy

import java.util.*;

public class Solution {
/**
* pick candy
* @param arr int整型一维数组 the array
* @return int整型
*/
public int candy (int[] arr) {
int len = arr.length;
int[] num = new int [len];
for(int i = 0; i < len; i++){
num[i] = 1;
}
for(int i = 1; i < len; i++){
if(arr[i-1] < arr[i]){
num[i] = num[i-1] + 1;
}
}
for(int i = len - 1; i > 0; i--){
if(arr[i] < arr[i-1] && num[i] >= num[i-1]){
num[i-1] = num[i] + 1;
}
}
int result = 0;
for(int i = 0; i < len; i++){
result = result + num[i];
}
return result;
}
}

发表于 2022-06-19 21:39:22 回复(0)

Java

紫薇爸爸

思路（贪心策略）：
注意：若两个孩子得分相同，分配糖果无限制，即不需要保证分数相同（相邻与否），得到的糖果数相同
1、先创建一个长度为arr.length，元素都为1的数组
2、从左往右看：索引值从 0 到length-2，看arr[i] 与 arr[i+1]的关系，如果arr[i]<arr[i+1]，则 i+1位置上的糖果比 i位置多给一个，即candy[i+1]=candy[i]+1;
3、从右往左看：索引值从 length-1 到 1，看arr[i] 与 arr[i-1]的关系，如果arr[i-1]>arr[i]，则 i-1位置上的糖果要保证比 i位置上的多，即candy[i-1]=Math.max(candy[i-1],candy[i]+1); 因为candy[i-1]可能已经在“从左往右看”的时候被再次赋值过，这个值有可能比candy[i]大，因此需要进行比较，选出最大的，这样可以保证糖果比左右的都要多，例如：分数序列123451，5就比1+1大
总结：从左往右，保证右边比左边大的时候，糖果数也大；从右往左，保证右边比左边大或相等的情况下，糖果数符合要求

import java.util.*;
public class Solution {
    public int candy (int[] arr) {
        // write code here
        int len = arr.length;
        if(len==0) return 0;
        if(len==1) return 1;
        int[] candy = new int[len];
        for(int i=0;i<len;i++){
            candy[i]=1;
        }
        for(int i=1;i<len;i++){
            if(arr[i]>arr[i-1]){
                candy[i]=candy[i-1]+1;
            }
        }
        for(int i=len-1;i>0;i--){
            if(arr[i-1]>arr[i]){
                candy[i-1] = Math.max(candy[i-1],candy[i]+1);
            }
        }
        int res=0;
        for(int i=0;i<len;i++){
            res+=candy[i];
        }
        return res;
    }
}

图片说明

发表于 2022-04-02 21:47:39 回复(0)

Java

顾子zz

前后遍历两遍，第一次记录递增，第二次记录递减

import java.util.*;


public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // write code here
        if(arr.length == 1)return 1;
        int[] candy = new int[arr.length];
        candy[0] = 1;
        for(int i = 1; i < arr.length; i++){
            candy[i] = 1;
            if(arr[i] > arr[i - 1]){
                candy[i] = candy[i - 1] + 1;
            }
        }
        int res = candy[arr.length - 1];
        for(int i = arr.length - 2; i >= 0; i--){
            if(arr[i] > arr[i + 1]){
                candy[i] = Math.max(candy[i], candy[i + 1] + 1);
            }
            res += candy[i];
        }
        return res;
    }
}

发表于 2022-03-25 18:06:45 回复(0)

Java

lianjun

import java.util.*;


public class Solution {

    public int candy (int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int n = arr.length;
        int[] nums = new int[n];
        // 先分一个
        Arrays.fill(nums, 1);
        // 得分比前一个多，需要保证糖果数量也比前一个多
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                nums[i] = nums[i - 1] + 1;
            }
        }
        // 得分比后一个多，需要保证糖果数量也比后一个多
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                if (nums[i] <= nums[i + 1]) {
                    nums[i] =  nums[i + 1] + 1;
                }
            }
        }
        int sum = 0;
        for (int num:nums) {
            sum += num;
        }
        return sum;
    }
}

发表于 2022-03-19 14:09:27 回复(0)