LeetCode算法题(Go语言实现)_03

题目

有 n 个有糖果的孩子。给你一个数组 candies，其中 candies[i] 代表第 i 个孩子拥有的糖果数目，和一个整数 extraCandies 表示你所有的额外糖果的数量。
返回一个长度为 n 的布尔数组 result，如果把所有的 extraCandies 给第 i 个孩子之后，他会拥有所有孩子中 最多 的糖果，那么 result[i] 为 true，否则为 false。
注意，允许有多个孩子同时拥有 最多 的糖果数目。

一、 Go 语言实现

func kidsWithCandies(candies []int, extraCandies int) []bool {
    maxCandy := 0
    // 找出所有孩子中的最大糖果数
    for _, c := range candies {
        if c > maxCandy {
            maxCandy = c
        }
    }
    // 遍历每个孩子，判断加上额外糖果后是否成为最大
    result := make([]bool, len(candies))
    for i, c := range candies {
        result[i] = (c + extraCandies) >= maxCandy
    }
    return result
}

二、 算法分析

1. 核心思路

• 最大值比较：所有额外糖果给当前孩子后，其糖果数是否达到或超过原始数组中的最大值。
• 关键观察：即使其他孩子未获得额外糖果，只要当前孩子加上 extraCandies 后不小于原始最大值，则他必然成为最大值或并列最大值。

2. 关键步骤

1. 找出最大值：遍历数组找到原始最大糖果数 maxCandy。
2. 判断条件：对每个孩子，判断 candies[i] + extraCandies >= maxCandy。

3. 复杂度

• 时间复杂度：O(n)，两次线性遍历数组。
• 空间复杂度：O(n)，存储结果数组。

图解

四、 边界条件与扩展

1. 空数组处理：题目保证 n ≥ 1，无需处理。
2. 全同糖果：所有孩子结果均为 true。
3. 额外糖果为 0：仅原始最大值对应的孩子为 true。

五、总结

• 核心逻辑：通过两次遍历快速判断每个孩子是否能成为最大值。
• 优化点：仅需比较原始最大值，无需动态计算其他孩子的当前值。
• 适用场景：类似“比较静态条件”的问题可借鉴此思路。