首页 > 试题广场 >

分糖果

[编程题]分糖果

热度指数：49913 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有N个小朋友站在一排，每个小朋友都有一个评分

你现在要按以下的规则给孩子们分糖果：

每个小朋友至少要分得一颗糖果
分数高的小朋友要他比旁边得分低的小朋友分得的糖果多

你最少要分发多少颗糖果？

示例1

输入

[1,2,2]

输出

算法知识视频讲解

CarsonZhu＆＆

class Solution {
public:
    int candy(vector<int> &ratings) {
        //题意：N个孩子站成一排，每个孩子分配一个分值。给这些孩子派发糖果，满足如下要求：
        //每个孩子至少一个
        //分值更高的孩子比他的相邻位的孩子获得更多的糖果
        //求至少分发多少糖果？
        int len=ratings.size();
        if(len==1) return 1;
        
        int sum=0;
        vector<int> v(len,1);//初始将每个孩子的糖果数都设为1
        
        //从左向右扫描，保证一个方向上分数更大的糖果更多
        for(int i=1;i<len;i++){
            if(ratings[i] > ratings[i-1])
                v[i]=v[i-1]+1;
        }
        //从右向左扫描，保证另一个方向上分数更大的糖果更多
        for(int i=len-2;i>=0;i--){
            if(ratings[i] > ratings[i+1] && v[i] <= v[i+1])
                v[i]=v[i+1]+1;
        }
        
        for(int i=0;i<len;i++){
            sum+=v[i];
        }
        return sum;
    }
};

发表于 2016-09-12 00:34:44 回复(10)

LinuX18

class Solution {
public:
  /*
  遍历两边，首先每个人得一块糖，第一遍从左到右，若当前点比前一个点高就比前者多一块。
  这样保证了在一个方向上满足了要求。第二遍从右往左，若左右两点，左侧高于右侧，但
  左侧的糖果数不多于右侧，则左侧糖果数等于右侧糖果数+1，这就保证了另一个方向上满足要求
 */
    int candy(vector<int> &ratings)
    {
        int n = ratings.size();
        if(n==0) return 0;
        vector<int> candy(n,1);
        for(int i=1;i<n;i++)
        {
            if(ratings[i] > ratings[i-1])
                candy[i] = candy[i-1]+1;
        }
        for(int i=n-1;i>=0;i--)
        {
            if(ratings[i-1] > ratings[i] && candy[i-1] <= candy[i])
                candy[i-1] = candy[i]+1;
        }
        return accumulate(candy.begin(),candy.end(),0);
    }
};

发表于 2017-07-06 14:49:47 回复(1)

C/C++

卷积神经网络哦

正向一次反向一次ok了

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n = ratings.size();
        int *dp = new int[n], sum = 0;
        for(int i=0;i<n;i++) dp[i] = 1;

        for(int i=1;i<n;i++)
           if(ratings[i] > ratings[i-1]) 
               dp[i] = dp[i-1] + 1;

        for(int i=n-1;i>0;i--)
            if(ratings[i-1] > ratings[i] && dp[i-1] <= dp[i]) 
                dp[i-1] = dp[i] + 1;

        for(int i=0;i<n;i++) sum += dp[i];
        return sum;
    }
};

发表于 2019-04-13 16:40:01 回复(0)

littleKang

import java.util.*;
public class Solution {
    public int candy(int[] ratings) {
        if(ratings==null || ratings.length==0) {
            return 0;
        }
        
        int[] count = new int[ratings.length];
        //每个孩子初始都有一个糖果
        Arrays.fill(count,1);
        int sum = 0;
        for(int i=1;i<ratings.length;i++) {
            if(ratings[i]>ratings[i-1]) {
                count[i] = count[i-1]+1;
            }
        }
        
        for(int i=ratings.length-1;i>0;i--) {
            sum+=count[i];
            if(ratings[i]<ratings[i-1] && count[i]>=count[i-1]) {
                count[i-1] = count[i]+1;
            }
        }
        sum+=count[0];
        
        return sum;
    }
}

发表于 2016-03-19 15:56:08 回复(11)

给点力啊大师兄

import java.util.Arrays;

public class Solution {     //状态转移方程为 candies[i] = max{candies[i-1], candies[i+1]} + 1
    public int candy(int[] ratings) {
        int sum = 0;
        int [] candies = new int [ratings.length];
        Arrays.fill(candies, 1);//把糖果数组初始化为1
        //从左向右使得当ratings[i] > ratings[i-1]时，candies[i] > candies[i-1]
        for(int i = 1; i < ratings.length; i++) {
            if(ratings[i] > ratings[i-1])
                candies[i] = Math.max(candies[i], candies[i-1] + 1);
        }
        //从右向左扫描，使得ratings[i] > ratings[i+1]时，candies[i] > candies[i+1]
        sum += candies[candies.length-1];
        for(int i = ratings.length-2; i >= 0; i--) {
            if(ratings[i] > ratings[i+1])
                candies[i] = Math.max(candies[i], candies[i+1] + 1);
            sum += candies[i];
        }

        return sum;
    }
}

发表于 2017-12-06 13:03:05 回复(0)

chenfengkg

（1）笨方法
动态规划思想（易于理解）：每个糖果的值都要受限与邻居结点（如果评估值比邻居结点大，那么得到的糖果也比邻居结点多）

根据限制我们可以想到一个二维数组，从初次扫描开始，每次扫描将评估值与同行前一个结点和前一行后一个结点的值比较，如果大于就加一。
何时结束：N个值，最多进行N次循环，因为最多N个不同的数，最大糖果差为N。
本题，使用NN的数组会超出内存限制，于是改用2N的数组，其实，也只用到两行，前一行，后一行。

    int candy(vector<int> &ratings) {
        vector<vector<int>>  v(2,vector<int>());
        for(int i = 0;i < ratings.size();i++){
            v[0].push_back(0);
            v[1].push_back(0);
        }
        //初始化，每个孩子一个糖果
        for(int i = 0;i < ratings.size();i++)
            v[0][i] = 1;

        bool bc = true;
        bool inturn = true;
        int pre,pos;
        for(int i = 1;i < ratings.size();i++){
            if(!bc) break;
            bc = false;
            //轮流切换两行
            if(inturn){
                pre = 0;
                pos = 1;
                inturn = false;
            } else{
                pre = 1;
                pos = 0;
                inturn = true;
            }
            //与左邻居和右邻居比较
            for(int j = 0;j < ratings.size();j++){
                v[pos][j] = v[pre][j];
                if(j>0){
                    if(ratings[j] > ratings[j-1]){
                        if(v[pre][j] <= v[pos][j-1]){
                            v[pos][j] = v[pos][j-1] + 1;
                            if(!bc) bc = true;
                        }
                    }
                }
                if(j<ratings.size()-1){
                    if(ratings[j] > ratings[j+1]){
                        if(v[pos][j] <= v[pre][j+1]){
                            v[pos][j] = v[pre][j+1] + 1;
                            if(!bc) bc = true;
                        }
                    }
                }
            }
        }
        int minCan = 0;
        if(inturn) pos = 0;
        else pos = 1;
        for(int i = 0;i < ratings.size();i++)
            minCan += v[pos][i];
        return minCan;
    }

（2）灵活方法
第一次从左向右扫描找到一个方向上的最大值，第二次从右向左扫描找到另一个方向的最大值。

从左向右扫描后能保证比左边邻居大1

从右向左扫描后能保证比右边邻居大1，同时因为第一次扫描，也可以保证比左边大1
为什么还要从右向左扫描，因为有可能右边邻居等于自身。
例如：2 1
输出应该为 3，只从左向右的，会输出2

int candy(vector<int> &ratings) {
    int n = ratings.size();
    vector<int> v(n,1);
    for( int i = 1;i < n;i++)
        if(ratings[i]>ratings[i-1]) v[i] = v[i-1]+1;
    int sum = 0;
    for( int i = n-1;i > 0;i--){
        if(ratings[i-1]>ratings[i]&&v[i-1]<=v[i]) v[i-1] = v[i] + 1;
        sum += v[i];
    }
    sum += v[0];
    return sum;
    }

同步博客

发表于 2017-11-28 15:29:36 回复(1)

sky_

dp做法：

class Solution {
public:
    int candy(vector<int> &ratings) {
        int r=ratings.size();
        map<int,int> mp;mp.clear();
        for(int i=0;i<r;i++) mp[i]=1;
        for(int i=0;i<r-1;i++){
            if(ratings[i]<ratings[i+1])
               mp[i+1]=mp[i]+1; 
        }
        int ans=0;
        for(int i=r-2;i>=0;i--)
            if(ratings[i]>ratings[i+1])
               mp[i]=max(mp[i],mp[i+1]+1);
        for(int i=0;i<r;i++) ans+=mp[i]; 
        return ans;
    }
};

拓扑排序做法（果然我dp还是弱到爆）

class Solution {
public:
    int candy(vector<int> &ratings) {
       queue<int> q;
       vector<int> G[100000];
       int ans=0,r=ratings.size(),indeg[100000],dp[100000];
       memset(indeg,0,sizeof(indeg));
       memset(dp,0,sizeof(dp)); 
       for(int i=0;i<r-1;i++){
           if(ratings[i]>ratings[i+1]) indeg[i]++,G[i+1].push_back(i);
           else if(ratings[i]<ratings[i+1]) indeg[i+1]++,G[i].push_back(i+1);
       } 
       for(int i=0;i<r;i++) if(!indeg[i]) dp[i]=1,q.push(i);
       while(q.size()){
           int u=q.front();q.pop();
           for(int j=0;j<G[u].size();j++){
               int v=G[u][j];
               dp[v]=max(dp[v],dp[u]+1);
               indeg[v]--;
               if(!indeg[v]) q.push(v);
           }
       }
        for(int i=0;i<r;i++) ans+=dp[i];
        return ans;
    }
};

编辑于 2017-04-14 13:29:43 回复(0)

后劲好大

先从左到右，再从右到左扫描两遍即可
public class Solution {
    public int candy(int[] ratings) {
        if(ratings == null || ratings.length <= 1)
        	return 1;
        
        int[] candy = new int[ratings.length];
        int sum = 0;
        for(int i = 0; i < candy.length; i++)
        	candy[i] = 1;
        for(int i = 1; i < candy.length; i++){
        	if(ratings[i] > ratings[i - 1])
        		candy[i] = candy[i - 1] + 1;
        }
        for(int i = candy.length - 1; i > 0; i--){
        	if(ratings[i] < ratings[i - 1] && candy[i] >= candy[i - 1])
        		candy[i - 1] = candy[i] + 1;
        }
        
        for(int i = 0; i < candy.length; i++)
        	sum += candy[i];
        
        return sum;
    }
}

发表于 2017-05-15 16:35:55 回复(0)

C++

牛客990571062号

分享个别的思路，用左右指针，使每次得到局部最优。基本思路就是分数高的在分数低的基础上加一块糖，分数一样或者低的就先只拿一块糖，后面根据指针按需补足。

class Solution {
public:
    /**
     * 
     * @param ratings int整型vector 
     * @return int整型
     */
    int candy(vector<int>& ratings) {
        // write code here
        int res = 1, pointer = 0, tmp=1, count =0;
        for (int i=1; i!=ratings.size(); ++i){
            if (ratings[i]>ratings[i-1]){
                pointer = i; //指针
                if (count != 0) tmp = 1;
                tmp++;  //tmp用于存储当前指针所指向的小朋友分到的糖果数量
                res += tmp;
                count =0;
            }
            else if(ratings[i]==ratings[i-1]){
                pointer = i;
                tmp=1;
                res += tmp;
                count =0;
            }
            else{
                res += i-pointer+1; //分数下降，则不移动指针，给指针到当前小朋友每人加一颗糖
                count ++;
                if (tmp>count) res --;
            }
        }
        return res;
    }
};

发表于 2022-01-09 07:28:55 回复(0)

牛客477902374号

public class Solution {
    public int candy(int[] ratings) {
        if(ratings == null || ratings.length==0) return 0;
        
        int[] dp = new int[ratings.length];
        dp[0] = 1;
        // dp[i]存储的是第i个孩子得到的糖果
        for(int i=1; i<ratings.length; i++) {
            if(ratings[i] > ratings[i-1]) {
                dp[i] = dp[i-1]+1;
                continue;
            }
            if(ratings[i] == ratings[i-1]) {
                dp[i] = 1;
                continue;
            }
            dp[i] = 1;
            if (dp[i] < dp[i-1]) {
                continue;
            }
            for(int j=i-1; j>=0; j--) {
                if (ratings[j]==ratings[j+1]) break;
                if (ratings[j]>ratings[j+1]&&dp[j]>dp[j+1]) break;
                if (ratings[j]<ratings[j+1]&&dp[j]<dp[j+1]) break;
                dp[j]+=1;
            }
        }
        
        int result = 0;
        for(int a:dp) result+=a;
        return result;
    }
}

发表于 2020-04-17 10:14:43 回复(0)

secndf

public class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0)
            return 0;
        int len = ratings.length, dp[] = new int[len], count = len;
        for (int i = 1; i < len; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            } else if (ratings[i] < ratings[i - 1]) {
                int j = i;
                while (j > 0 && ratings[j] < ratings[j - 1] && dp[j] >= dp[j - 1])
                    dp[j - 1] = dp[j--] + 1;
            }
        }
        for (int i = 0; i < len; ++i)
            count += dp[i];
        return count;
    }
}

发表于 2019-01-23 19:16:11 回复(0)

差不多就行啦

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n = ratings.size();
        vector<int> res(n,1);
        for(int i = 0; i < n; i++){
            if(ratings[i+1] > ratings[i]){
                res[i+1] = res[i] + 1;
            }
        }
        for(int i = n-1; i >=1; i--){
            if(ratings[i-1] > ratings[i] && res[i-1] <= res[i]){
                res[i-1] = res[i] + 1;
            }
        }
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += res[i];
        }
        return sum;
    }
};

发表于 2018-07-27 20:54:33 回复(0)

C/C++

华为招聘专员007

这道题目采用动态规划的思想来求解，我觉得思想很重要

分为以下几个步骤：

1）当前孩子的rating比前面的孩子的rating高时：只需要考虑当前孩子的candies数目比前面孩子的candies的数目多至少一个即可；当前面的rating等于后面孩子的rating时，则题目没有说明，则可以比他多或者少；

2）当前孩子的rating比后面孩子的raitng低时：考虑当前孩子的后面的单调递减的孩子的数目，因为最后一个单调递减的孩子的手里至少还剩下一个糖果存在，则新建一个数组来存储单调递减孩子的数目，并将当前孩子的手里的糖果的数目设定为单调递减孩子的数目+1；

3）判断左边动态规划和右边动态规划的糖果数目，取其中糖果数目最大的即可；

代码如下：

class Solution {
public:
int candy(vector<int> &ratings) {
if(ratings.size()==0)
return -1;
int length=ratings.size();
vector<int> array(length);
for(int i=0;i<length;i++){
int space=0;
for(int j=i+1;j<length;j++){
if(ratings[j]>=ratings[j-1])
break;
else{
space++;
}
}
array[i]=space;
}

int result=0;
vector<int>candies(length);
candies[0]=array[0]+1;
result+=candies[0];

for(int i=1;i<length;i++){
int leftcandies=0;
if(ratings[i]>ratings[i-1])
leftcandies=candies[i-1]+1;
int rightcandies=array[i]+1;
candies[i]=max(leftcandies,rightcandies);
result+=candies[i];

}
return result;

}
};

发表于 2018-07-21 22:00:00 回复(1)

C/C++

nbgao

class Solution {
public:
    int candy(vector<int> &ratings) {
        int l = ratings.size();         if(l == 1)             return 1;         int s = 0;         vector<int> a(l,1);                  for(int i=1;i<l;i++)             if(ratings[i] > ratings[i-1])                 a[i] = a[i-1] + 1;                  for(int i=l-2;i>=0;i--)             if(ratings[i] > ratings[i+1] && a[i] <= a[i+1])                 a[i] = a[i+1] + 1;                  for(int i=0;i<l;i++)             s += a[i];                  return s;
    }
};

发表于 2017-09-25 01:16:23 回复(0)

C/C++

牛客7311123

class Solution {

public:

int candy(vector<int> &rat) {

vector<int> num(rat.size()+1,1);

for(int i=1;i<rat.size();i++){

if(rat[i]>rat[i-1]) num[i]=num[i-1]+1;

else{

int j=i-1;

while(j>=0 && rat[j]>rat[j+1] && num[j]<=num[j+1]){ num[j]+=1; j--; }

}

int res=0;

for(int i=0;i<rat.size();i++) res+=num[i];

return res;

}

};

发表于 2017-09-07 20:55:21 回复(0)

梦游计

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n = ratings.size();
        int dp[n];

        dp[0] = 1;

        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                dp[i] = max(dp[i], dp[i + 1] + 1);
            }
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += dp[i]; 
        }

        return sum;
    }
};

发表于 2017-08-30 17:53:49 回复(0)

Hotwill

class Solution {
public:
	int candy(vector<int> &ratings) {
        vector<pair<int, int>> v;
        for (int i = 0; i < ratings.size(); ++i)
            v.push_back({ ratings[i], i });
        sort(v.begin(), v.end(), [](const pair<int, int> &a, const pair<int, int> &b) {return a.first < b.first;});

        vector<int> candies(ratings.size(), 0);
        int n_count = 0;
        for (auto e : v) {
            int i = e.second;
            int left = 0;
            if (i - 1 >= 0) left = candies[i - 1];
            int right = 0;
            if (i + 1 < candies.size()) right = candies[i + 1];

            candies[i] = 1;
            if (left != 0 && ratings[i - 1] < ratings[i])
                candies[i] = left + 1;
            if (right != 0 && ratings[i + 1] < ratings[i])
                candies[i] = max(candies[i], right + 1);

            n_count += candies[i];
        }

        return n_count;
    }
};

发表于 2017-08-06 15:50:59 回复(0)

Java

詆調壹點

import java.util.*;
public class Solution {
    public int candy(int[] ratings) {
		int[] arr1 = new int[ratings.length];
		int[] arr2 = new int[ratings.length];
		Arrays.fill(arr1, 1);
		Arrays.fill(arr2, 1);
		for (int i = 1; i < ratings.length; i ++) {
			if(ratings[i] > ratings[i - 1]) arr1[i] = arr1[i - 1] + 1;
		}
		for (int i = ratings.length - 1; i >= 1; i --) {
			if(ratings[i] < ratings[i - 1]) arr2[i - 1] = arr2[i] + 1;
		}
		int sum = 0;
		for (int i = 0; i < ratings.length; i ++) {
			sum += arr1[i] > arr2[i] ? arr1[i] : arr2[i];
		}
		return sum;
	}
}

编辑于 2017-03-19 17:04:09 回复(0)

不负时光

class Solution {
public:
    int candy(vector<int>& ratings) {
        int ret = 0;
        int len = ratings.size();
        vector<int> temp(len, 1);
        for(int i = 1; i < len; i++){
            if(ratings[i] > ratings[i-1]){
                temp[i] = temp[i-1]+1;
            }
        }
        for(int i = len-2; i >= 0; i--){
            if(ratings[i] > ratings[i+1]){
                temp[i] = max(temp[i], temp[i+1]+1);
            }
        }
        for(int i = 0; i < len; i++){
            ret += temp[i];
        }
        return ret;
    }
};

发表于 2016-09-06 16:52:31 回复(0)

Joe2016

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n=ratings.size();
        if(n==0) return 0;
        
        vector<int> res(n);//存每个小孩应发的糖果数
        res[0]=1;
        for(int i=1;i<n;i++){//不断遍历ratings并更新res
            //如果新加入的小孩大于前一个小孩，则糖果比前一个小孩+1
            if(ratings[i]>ratings[i-1]) {
                res[i]=res[i-1]+1;
            }
            //关键：如果等于前一个小孩，则新小孩只需要分一个糖果，res不需要更新
            else if(ratings[i]==ratings[i-1]) {
                    res[i]=1;
            }
            //如果小于前一个小孩,则新加入小孩分一个糖果，之前的小孩应该比他多分到糖果  
            else{
                res[i]=1;
                //如果前面的小孩只有一个糖果，需要更新res
                if(res[i-1]==1) {
                    
                    //前面的小孩都多分一个糖果，直到递增结束
                    int j=i-1;
                    for(;j!=0&&res[j]<res[j-1];j--){
                        res[j]++;
                    }
                    //关键：注意相等rating的情况
                    if(res[j]<=res[j+1] && ratings[j]!=ratings[j+1])res[j]++;
                }
            }
            
        }
        int sum=0;
        for(auto e:res){
            sum+=e;
        }
        return sum;
    }
};

发表于 2016-07-04 01:27:26 回复(0)