题目描述
思路解析动画文字版
记牢一句:先扫一遍求出全场最大 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题