题目描述
思路解析
一句话答案：LeetCode 1431 拥有最多糖果的孩子：先一遍求出全场最大糖果 mx，再看每个孩子 candies[i]+extra 是否 ≥ mx，达到就并列最多标 true，时间 O(n)、空间 O(1)。
把额外糖果全给一个孩子，他能不能追上最多
有 n 个孩子，candies[i] 是第 i 个孩子手里的糖果数，你手上另有一份 extraCandies，这份额外糖果是「整份」的，要给就全给某一个。对每个孩子单独问一次：假设把这一整份都给他，他会变成 candies[i]+extraCandies 颗，这个新数值是不是全场最多？题目允许并列——追平当前最多就算，不必严格超过。额外糖果判完不会真发掉，下一个孩子还能再假设拿到同一份。题面例子 candies=[2,3,5,1,3]、extraCandies=3，答案是 [true,true,true,false,true]。
每判一个孩子都跟全场逐个比，代价有多大
有一种做法是：判第 i 个孩子时，把 candies[i]+extra 和数组里每个数逐个比过去，看有没有人更高。可这样每个孩子都要跟全场比一圈，n 个孩子各比 n 次，一共 n×n 次，就是 O(n²)。这些重复全在做无用功——全场最大是个固定的数，跟判谁无关，没必要一遍遍重算。
先把全场最大定死，比较为什么得用大于等于
既然全场最大 mx 是固定的，就先花一遍把它求出来存着反复用。判第 i 个孩子只做一次加法加一次比较：candies[i]+extra 只要不小于 mx，他就追平或超过了当前最多，标 true。省下的正是朴素做法里那 n 遍重复的求最大。
比较必须写 ≥，不能写严格大于。某个孩子加完正好等于 mx，也算并列到了最多，该标 true；写成严格＞会把这种「刚好追平」误判成 false。反过来，本来就持有 mx 的孩子，额外糖果至少 1 颗，加完必然＞mx，一定是 true——所以答案里至少有一个 true，永远不会全是 false。
[2,3,5,1,3] 配 extra=3，五个格子怎么填出来
第一遍求 mx。从 mx=0 起手，看 2＞0 把 mx 提到 2，看 3＞2 提到 3，看 5＞3 提到 5，再看 1 和 3 都没超过 5，mx 停在 5，来自第 2 个孩子的那 5 颗糖。
第二遍逐个加 3 再和 5 比：第 0 个孩子 2+3=5，5 不小于 5，true；第 1 个 3+3=6，6≥5，true；第 2 个 5+3=8，8≥5，true；第 3 个 1+3=4，4 比 5 还小，false；第 4 个 3+3=6，6≥5，true。五个格子填完就是 [true,true,true,false,true]。
求最大只做一次，别让它溜进第二遍循环
最容易悄悄拖垮性能的，是把求全场最大写进判定每个孩子的循环——实则把一遍 O(n) 的求最大做了 n 遍，整体滑到 O(n²)。它只该在判定之前独立做一次，钉在 mx 上反复取用。另一处坑在比较符：允许并列就得用 ≥，用严格＞会漏掉加完刚好追平最大值的孩子。还有人以为额外糖果给了一个就少一份，其实每个孩子都是各自独立的假设，判完原样归位，比的始终是同一个 mx。
复杂度上，两遍线性扫描相加仍是 O(n)；除了必须交出去的那个长度为 n 的结果数组，只多用了 mx 和循环变量几个常数空间，辅助空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句:先扫一遍求出全场最大 mx,再对每个孩子看 candies[i]+extra 是否 ≥ mx,是就 true。比较用 ≥ 不用 >,因为最多允许并列。下面每帧都在套这句。
总览 · 糖果数组 + 额外糖果：画面摆好了。上面这排是五个孩子各自的糖果数 [2,3,5,1,3],右边状态栏记着额外糖果 extra 等于 3,还有待求的全场最大 mx,以及一个全是问号的结果数组。我们分两步走:先扫一遍把全场最大找出来,再回头逐个孩子判定。先进第一步求最大。
第一步 · 初始化 mx = 0：第一步要找全场最大糖果数。先把记最大值的变量 mx 设成 0,因为题目保证每个孩子至少有 1 颗糖,从 0 起步一定会被真实数据更新。接下来从左到右一个一个看,谁比 mx 大就把 mx 换成谁。
第一步 · 看 candies[0] = 2：看第 0 个孩子,糖果数是 2,它比当前的 mx 也就是 0 大,所以 mx 被刷新成 2。绿色标出的就是目前持有最大值的位置。
第一步 · 看 candies[1] = 3：看第 1 个孩子,糖果数是 3,它比当前的 mx 也就是 2 大,所以 mx 被刷新成 3。绿色标出的就是目前持有最大值的位置。
第一步 · 看 candies[2] = 5：看第 2 个孩子,糖果数是 5,它比当前的 mx 也就是 3 大,所以 mx 被刷新成 5。绿色标出的就是目前持有最大值的位置。
第一步 · 看 candies[3] = 1：看第 3 个孩子,糖果数是 1,它没有超过当前的 mx 也就是 5,所以 mx 不动,还是 5。绿色仍然标在持有最大值的那个孩子身上。
第一步 · 看 candies[4] = 3：看第 4 个孩子,糖果数是 3,它没有超过当前的 mx 也就是 5,所以 mx 不动,还是 5。绿色仍然标在持有最大值的那个孩子身上。
第一步完成 · 全场最大 mx = 5：一整遍扫完,mx 锁定在 5,来自第 2 个孩子的 5 颗糖,绿色标出的就是它。第一步结束。注意这里 mx 是「现在」的全场最大,还没算额外糖果。接下来第二步,我们要看每个孩子拿到额外糖果之后,能不能追平这个 5。
第二步 · 判定规则就一句：进第二步。规则浓缩成一句:对第 i 个孩子,算 candies[i] 加上额外的 3,只要这个和不小于全场最大 5,他就能并列或超过最多,标 true,否则标 false。比较务必用「大于等于」,因为达到 5 就算最多。下面从第 0 个孩子开始,一个一个填结果。
第 0 个孩子 · 先算拿到额外糖果后的总数：轮到第 0 个孩子,他现在有 2 颗糖。假设把额外的 3 颗全给他,总数就是 2 加 3 等于 5 颗。先把这个总数算出来,再去跟全场最大 5 比。
第 0 个孩子 · 比较得 true：拿 5 跟全场最大 5 比,5 不小于 5,说明他追平或超过了最多,result[0] 填 true,绿色点亮。
第 1 个孩子 · 先算拿到额外糖果后的总数：轮到第 1 个孩子,他现在有 3 颗糖。假设把额外的 3 颗全给他,总数就是 3 加 3 等于 6 颗。先把这个总数算出来,再去跟全场最大 5 比。
第 1 个孩子 · 比较得 true：拿 6 跟全场最大 5 比,6 不小于 5,说明他追平或超过了最多,result[1] 填 true,绿色点亮。
第 2 个孩子 · 先算拿到额外糖果后的总数：轮到第 2 个孩子,他现在有 5 颗糖。假设把额外的 3 颗全给他,总数就是 5 加 3 等于 8 颗。先把这个总数算出来,再去跟全场最大 5 比。
第 2 个孩子 · 比较得 true：拿 8 跟全场最大 5 比,8 不小于 5,说明他追平或超过了最多,result[2] 填 true,绿色点亮。
第 3 个孩子 · 先算拿到额外糖果后的总数：轮到第 3 个孩子,他现在有 1 颗糖。假设把额外的 3 颗全给他,总数就是 1 加 3 等于 4 颗。先把这个总数算出来,再去跟全场最大 5 比。
第 3 个孩子 · 比较得 false：拿 4 跟全场最大 5 比,4 比 5 还小,他够不到最多,result[3] 填 false,蓝色表示判过但不达标。
第 4 个孩子 · 先算拿到额外糖果后的总数：轮到第 4 个孩子,他现在有 3 颗糖。假设把额外的 3 颗全给他,总数就是 3 加 3 等于 6 颗。先把这个总数算出来,再去跟全场最大 5 比。
第 4 个孩子 · 比较得 true：拿 6 跟全场最大 5 比,6 不小于 5,说明他追平或超过了最多,result[4] 填 true,绿色点亮。
完成 · result = [true,true,true,false,true]：五个孩子都判完了,回看一遍:第 0、1、2 个孩子加上额外的 3 颗分别是 5、6、8,都不小于全场最大 5,全是 true;第 3 个孩子只有 1 颗,加 3 才 4,够不到 5,是 false;第 4 个孩子加 3 是 6,达标,又是 true。最终 result 就是 [true,true,true,false,true],跟开头说的一字不差。整道题就是两遍扫描:一遍找最大,一遍逐个比。
边界:糖果相同则并列全 true(靠 ≥);额外糖果少时可能只有原最大者达标;本身就是最大的孩子加额外糖果后必然 true。
面试重点:两遍扫描共 O(n),求最大只做一次;比较用 ≥ 因允许并列;额外糖果≥1 故原最大者必 true,答案不会全 false。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]: mx = max(candies) return [candy + extraCandies >= mx for candy in candies]复杂度
- 时间：O(n)，n 是孩子个数。第一遍扫一遍 candies 求最大是 O(n),第二遍再扫一遍逐个判定也是 O(n),两遍相加仍是 O(n)。注意求最大要在循环外只做一次,千万别在判定每个孩子时都重新求一遍最大,那会退化成 O(n²)
- 空间：O(1)，按峰值算,除了必须交出去的长度为 n 的结果数组(这部分是输出,O(n)),额外只用了 mx 和循环变量这几个常数空间,所以辅助空间是 O(1)。Java 装布尔用的 ArrayList、C++ 的 vector 也都是承载输出的容器,不算额外增长
易错点
面试追问把动画讲成自己的话
追问为什么时间复杂度是 O(n),能不能一遍扫完?
追问比较为什么要用大于等于而不是严格大于?
追问结果数组有没有可能全是 false?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
重新排列数组
LeetCode 1470 · 简单 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题