LeetCode 1431. 拥有最多糖果的孩子

约 4 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 LeetCode 75 图森
标签
数组

题目描述

✅ 1431. 拥有最多糖果的孩子

image-20260929082548437

image-20260929082548541

题意分析

对每个孩子分别作一次假设：把全部额外糖果都给这个孩子，判断他能否达到所有孩子中的最多糖果数，并列最多也算。按原孩子顺序返回每个人的布尔结果。

各个假设相互独立，不是真的把同一批糖果依次分出去。判断下一个孩子时，仍使用原来的糖果数量和完整的额外数量，其余孩子的糖果也没有变化。

解法：全局最大值 + 逐项判断

核心思路

[!blue]

所有假设都面对同一份原始分布，可以先完整扫描一次，求出原来的最大值 maximum。判断第 i 个孩子时，只需比较 candies[i] + extraCandies 是否达到这个值。

如果加糖后达到原最大值，就不会比任何未变化的孩子少，因而可以成为最多之一。如果加糖后仍低于原最大值，持有那个最大值的其他孩子就仍比他多，不能成功。

原来已经最多的孩子也可以使用同一规则：额外糖果不会减少他的数量，他仍能达到原最大值，因此不需要专门排除自己或寻找第二大值。比较中保留等号，就自然接受并列最多。

第一遍只求完整最大值，第二遍再逐项判断。若一边扫描一边仅依据当前前缀最大值输出，前面的孩子可能还没有与后面的真正最大值比较，无法保证结论正确。

解题步骤

  1. 扫描全部孩子，得到原糖果数量的最大值。
  2. 按原顺序计算每个孩子的原数量加完整额外数量。
  3. 若结果不小于原最大值，记录 true，否则记录 false。
  4. 返回布尔数组，不修改输入糖果数量。

代码实现

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int maximum = 0;

        for (int candy : candies) {
            maximum = Math.max(maximum, candy);
        }

        // 先得到完整最大值，再为每个孩子独立作假设。
        List<Boolean> answer = new ArrayList<>(candies.length);

        for (int candy : candies) {
            // 达到相同最大值也算成功，不能去掉等号。
            answer.add(candy + extraCandies >= maximum);
        }

        return answer;
    }
}

func kidsWithCandies(candies []int, extraCandies int) []bool {
    maximum := 0
    for _, candy := range candies {
        if candy > maximum {
            maximum = candy
        }
    }

    // 先得到完整最大值，再为每个孩子独立作假设。
    answer := make([]bool, len(candies))
    for i, candy := range candies {
        // 达到相同最大值也算成功，不能去掉等号。
        answer[i] = candy+extraCandies >= maximum
    }
    return answer
}

复杂度分析

设孩子数量为 $n$。

  • 时间复杂度：$O(n)$，寻找最大值和逐项判断各扫描一次。
  • 辅助空间复杂度：$O(1)$，只维护全局最大值；返回结果占 $O(n)$。

关键点总结

[!green]

  • 每个孩子独立假设拿到全部额外糖果，共用原来的全局最大值。
  • 达到最大值即可，允许并列，不要求严格超过。
  • 两次扫描保留原顺序，不需要排序或实际分配糖果。

易错点总结

[!yellow]

  • 只使用严格大于会把并列最多误判为失败。
  • 使用前缀最大值而不是完整最大值，会漏掉后面更强的比较对象。
  • 将额外糖果逐次消耗，或累积修改 candies，会把独立假设误做成连续发糖。
  • 排序后直接输出会改变孩子与答案位置的对应关系，题目只需求一次极值即可。

相似题目

题目 难度 关联与区别
747. 至少是其他数字两倍的最大数 简单 同样先找全局极值，再验证数值阈值，本题逐个判断加糖后能否达到当前最大值。
1299. 将每个元素替换为右侧最大元素 简单 原题为每个位置维护右侧最大值，本题比较范围是全数组，只需一个全局最大值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/30942086
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！