1431. 拥有最多糖果的孩子

Easy

题目描述

有 n 个有糖果的孩子。给你一个整数数组 candies，其中每个 candies[i] 代表第 i 个孩子拥有的糖果数目，和一个整数 extraCandies，表示你拥有的额外糖果数目。

返回一个长度为 n 的布尔数组 result，其中 result[i] 为 true 当且仅当在给第 i 个孩子所有的 extraCandies 后，他将拥有所有孩子中最多的糖果，否则为 false。

注意，允许有多个孩子同时拥有最多的糖果数目。

示例 1：

输入：candies = [2,3,5,1,3], extraCandies = 3
输出：[true,true,true,false,true] 
解释：如果你把所有额外的糖果给：
- 孩子1，他将有 2 + 3 = 5 颗糖果，这是孩子们中最多的。
- 孩子2，他将有 3 + 3 = 6 颗糖果，这是孩子们中最多的。
- 孩子3，他将有 5 + 3 = 8 颗糖果，这是孩子们中最多的。
- 孩子4，他将有 1 + 3 = 4 颗糖果，这不是孩子们中最多的。
- 孩子5，他将有 3 + 3 = 6 颗糖果，这是孩子们中最多的。

示例 2：

输入：candies = [4,2,1,1,2], extraCandies = 1
输出：[true,false,false,false,false] 
解释：只有1个额外糖果。
孩子1总是拥有最多的糖果，即使不同的孩子得到额外的糖果。

示例 3：

输入：candies = [12,1,12], extraCandies = 10
输出：[true,false,true]

约束条件：

• n == candies.length
• 2 <= n <= 100
• 1 <= candies[i] <= 100
• 1 <= extraCandies <= 50

解题思路

解题思路

这道题目的核心在于判断每个孩子在获得所有额外糖果后，是否能成为拥有最多糖果的孩子。

基本思路：

1. 首先找到当前所有孩子中拥有糖果的最大值
2. 对于每个孩子，判断他当前的糖果数加上所有额外糖果是否大于等于最大值
3. 如果满足条件，说明这个孩子能够成为拥有最多糖果的孩子之一

具体步骤：

1. 遍历数组找到最大值 maxCandies
2. 对每个孩子 i，检查 candies[i] + extraCandies >= maxCandies 是否成立
3. 将结果存入布尔数组并返回

这个方法时间复杂度为 O(n)，空间复杂度为 O(1)（不考虑结果数组）。

算法优化： 可以在一次遍历中同时找最大值和计算结果，但为了代码清晰，通常采用两次遍历的方式。

代码实现

class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        int maxCandies = *max_element(candies.begin(), candies.end());
        vector<bool> result;
        
        for (int candy : candies) {
            result.push_back(candy + extraCandies >= maxCandies);
        }
        
        return result;
    }
};

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        max_candies = max(candies)
        return [candy + extraCandies >= max_candies for candy in candies]

public class Solution {
    public IList<bool> KidsWithCandies(int[] candies, int extraCandies) {
        int maxCandies = candies.Max();
        List<bool> result = new List<bool>();
        
        foreach (int candy in candies) {
            result.Add(candy + extraCandies >= maxCandies);
        }
        
        return result;
    }
}

var kidsWithCandies = function(candies, extraCandies) {
    const maxCandies = Math.max(...candies);
    return candies.map(candy => candy + extraCandies >= maxCandies);
};

复杂度分析