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

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

题目描述

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

题意分析

给一个数组 candies 和一个整数 extraCandies，要为每个孩子回答一个是非问题：把这 extraCandies 颗糖全部给他之后，他手里的糖是不是所有孩子里最多的（允许并列最多）。输出是一个与输入等长的布尔数组。

有两个措辞必须抠死。第一，extraCandies 是假设性地给某一个孩子，每个孩子的判断都是独立的一次假设，糖不会被累计消耗掉，所以判断第 i 个孩子时其余孩子的糖数仍然是原始值。第二，「最多」是 ≥ 而不是 >，题面说的是「拥有最多糖果」，并列第一也算，所以比较必须用 >=。

约束里透露的信号很直接：数组长度和数值都很小（最多几十个孩子、糖数不超过 100），$O(n^2)$ 的两两比较也能过。但真正决定写法的不是数据量，而是「其余孩子的糖数在整个过程中不会变」这个性质——它意味着所有孩子的判断可以共用同一个参照物，不需要每次都重新扫一遍别人。

边界只有两类：数组只有一个孩子时，他自己就是最大，答案恒为 true；所有孩子糖数完全相同时，加上任意非负的 extraCandies 后每个人都不低于最大值，答案全是 true。题目保证 extraCandies >= 1、candies[i] >= 1，不存在空数组和负数。

解法：模拟流程

核心思路

每个孩子的判断都是独立假设，其他孩子的糖数始终不变。因此所有位置可以共用同一个阈值 maximum = max(candies)，无需为每个孩子重新寻找对手。

第一趟扫描求出原数组最大值；第二趟对每个 candies[i] 判断

\[candies[i] + extraCandies \ge maximum\]

循环不变量是：第二趟处理到位置 i 前，maximum 已是完整输入的最大值，结果中的前 i 个布尔值均已正确对应原数组前 i 个孩子。

正确性直接来自充要条件：若不等式成立，该孩子加糖后至少与原最大值并列，而其他孩子都不超过原最大值，所以答案为真；若不成立，原先持有最大值的孩子仍严格更多，所以答案为假。

解题步骤

  • 扫描 candies 得到全局最大值 maximum。
  • 按原顺序再次扫描，对每个孩子计算 candies[i] + extraCandies >= maximum。
  • 将布尔结果写入同一位置并返回。

例如 candies = [2,3,5,1,3]、extraCandies = 3，最大值为 5，逐项判断得到 [true,true,true,false,true]。第一个孩子恰好达到 5，说明比较符必须是 >=。

单元素数组自然返回 [true]；所有孩子糖数相等时结果全为真。不能在同一趟中边更新前缀最大值边立即判定，否则 [1,100] 的第一个孩子会使用错误阈值。

代码实现

import java.util.ArrayList;
import java.util.List;

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
}

复杂度分析

  • 时间复杂度：$O(n)$，两趟线性扫描。
  • 空间复杂度：返回数组占 $O(n)$；不计输出只使用一个最大值变量，为 $O(1)$。

关键点总结

  • 每个孩子都是独立假设，extraCandies 不会在孩子之间消耗或累加。
  • 原数组的全局最大值是所有判断共享的固定阈值。
  • 使用包含自身的最大值即可；原本最大的孩子必然仍满足条件。
  • “最多”允许并列，比较符必须是 >=。
  • 结果顺序与输入孩子顺序一一对应，不能排序。

易错点总结

  • 把 >= 写成 >：样例中第一个孩子加糖后恰好为 5，并列最多也应为真。
  • 边求前缀最大值边判定：candies=[1,100] 时第一个孩子看不到后面的 100，可能被误判为真。
  • 把额外糖果逐个消耗：各位置是独立情景，不是依次发糖；[1,1,1]、额外 1 颗应全部为真。
  • 求“除自己外的最大值”：既增加复杂度，也会给单元素数组制造空集合边界；全局最大值已经足够。
  • Go 预分配长度后又使用 append：会得到长度 2n 的切片；当前代码按下标写入。

相似题目

题目 难度 考察点
121. 买卖股票的最佳时机 简单 同为一次扫描维护极值，但极值必须边走边用，不能先求全局再回头
414. 第三大的数 简单 要同时维护前三大而非单个最大值，去重和不足三个的返回值是难点
169. 多数元素 简单 目标从「最大值」换成「出现次数过半的值」，用抵消而非取最大
605. 种花问题 简单 同为逐位判定，但判定依据是左右邻居的局部关系而非全局统计量
1480. 一维数组的动态和 简单 同样输出等长数组，但每一位依赖前缀累计结果而不是全局常量