题目:给你一个数组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; } }