1431.拥有最多糖果的孩子

简介: 1431.拥有最多糖果的孩子

题目:给你一个数组candies和一个整数extraCandies,其中candies[i] 代表第i个孩子拥有的糖果数目。

对每一个孩子,检查是否存在一种方案,将额外的 extraCandies 个糖果分配给孩子们之后,此孩子有 最多 的糖果。注意,允许有多个孩子同时拥有 最多 的糖果数目。

解题思路:如果我们希望某个小朋友拥有的糖果最多,那么最优的方案当然是把额外的所有糖果都分给这个小朋友。因此,我们可以枚举每一个小朋友,并将额外的所有糖果都分给这个小朋友,然后再用 O(n) 的时间遍历其余的小朋友,就可以判断这个小朋友是否拥有最多的糖果。

上述方法的时间复杂度为 O(n^2),然而我们可以将其优化为 O(n)。事实上,对于每一个小朋友,只要这个小朋友「拥有的糖果数目」加上「额外的糖果数目」大于等于所有小朋友拥有的糖果数目最大值,那么这个小朋友就可以拥有最多的糖果。

class Solution{
    public List<Boolean>kidsWithCandies(int []candies,int extraCandies){
        int n=candies.length;
        int maxCandies=0;
        for(int i=0;i<n;++i){
           maxCandies=Math.max(maxCandies,candies[i]);         
        } 
        List<Boolean>ret =new ArrayList<Boolean>();
        for(int i=0;i<n;++i){
            ret.add(candies[i]+extraCandies>=maxCandies);        
        }   
        return ret;
    }
}


相关文章
|
5月前
LeetCode575——分糖果
LeetCode575——分糖果
25 0
|
6月前
|
算法 测试技术
联想算法题-小朋友分糖果
联想算法题-小朋友分糖果
39 0
|
6月前
LeetCode 20200601 打卡 1431. 拥有最多糖果的孩子
LeetCode 20200601 打卡 1431. 拥有最多糖果的孩子
23 0
wustojc2013分糖果
wustojc2013分糖果
42 0
wustojc2013分糖果
动态规划——糖果
动态规划——糖果
73 0
|
Java C++
多重背包(小明的背包3)
多重背包(小明的背包3)
|
C++
分糖果(C++)
Alice 非常喜欢这些糖,她想要在遵循医生建议的情况下,尽可能吃到最多不同种类的糖。Alice 注意到她的体重正在增长,所以前去拜访了一位医生。医生建议 Alice 要少摄入糖分,只吃掉她所有糖的。枚糖的情况下,可以吃到糖的 最多 种类数。,返回: Alice 在仅吃掉。给你一个长度为 n 的整数数组。
136 0