拥有最多糖果的孩子 图解题解
这道题到底在问什么
- 输入
- candies=[1,1], extra=1
- 输出
- [true,true]
- 输入
- candies=[4,2,1,1,2], extra=1
- 输出
- [true,false,false,false,false]
- 输入
- candies=[12,1,12], extra=10
- 输出
- [true,false,true]
先想最直接的笨办法
第一步要找全场最大糖果数。先把记最大值的变量 mx 设成 0,因为题目保证每个孩子至少有 1 颗糖,从 0 起步一定会被真实数据更新。接下来从左到右一个一个看,谁比 mx 大就把 mx 换成谁。（动画第 5 步）
最优解：一步一步想明白
- 3记牢一句:先扫一遍求出全场最大 mx,再对每个孩子看 candies[i]+extra 是否 ≥ mx,是就 true。比较用 ≥ 不用 >,因为最多允许并列。下面每帧都在套这句。
- 4画面摆好了。上面这排是五个孩子各自的糖果数 [2,3,5,1,3],右边状态栏记着额外糖果 extra 等于 3,还有待求的全场最大 mx,以及一个全是问号的结果数组。我们分两步走:先扫一遍把全场最大找出来,再回头逐个孩子判定。先进第一步求最大。
- 5第一步要找全场最大糖果数。先把记最大值的变量 mx 设成 0,因为题目保证每个孩子至少有 1 颗糖,从 0 起步一定会被真实数据更新。接下来从左到右一个一个看,谁比 mx 大就把 mx 换成谁。
- 6看第 0 个孩子,糖果数是 2,它比当前的 mx 也就是 0 大,所以 mx 被刷新成 2。绿色标出的就是目前持有最大值的位置。
- 7看第 1 个孩子,糖果数是 3,它比当前的 mx 也就是 2 大,所以 mx 被刷新成 3。绿色标出的就是目前持有最大值的位置。
- 8看第 2 个孩子,糖果数是 5,它比当前的 mx 也就是 3 大,所以 mx 被刷新成 5。绿色标出的就是目前持有最大值的位置。
- 9看第 3 个孩子,糖果数是 1,它没有超过当前的 mx 也就是 5,所以 mx 不动,还是 5。绿色仍然标在持有最大值的那个孩子身上。
- 10看第 4 个孩子,糖果数是 3,它没有超过当前的 mx 也就是 5,所以 mx 不动,还是 5。绿色仍然标在持有最大值的那个孩子身上。
- 11一整遍扫完,mx 锁定在 5,来自第 2 个孩子的 5 颗糖,绿色标出的就是它。第一步结束。注意这里 mx 是「现在」的全场最大,还没算额外糖果。接下来第二步,我们要看每个孩子拿到额外糖果之后,能不能追平这个 5。
- 12进第二步。规则浓缩成一句:对第 i 个孩子,算 candies[i] 加上额外的 3,只要这个和不小于全场最大 5,他就能并列或超过最多,标 true,否则标 false。比较务必用「大于等于」,因为达到 5 就算最多。下面从第 0 个孩子开始,一个一个填结果。
- 13轮到第 0 个孩子,他现在有 2 颗糖。假设把额外的 3 颗全给他,总数就是 2 加 3 等于 5 颗。先把这个总数算出来,再去跟全场最大 5 比。
- 14拿 5 跟全场最大 5 比,5 不小于 5,说明他追平或超过了最多,result[0] 填 true,绿色点亮。
- 15轮到第 1 个孩子,他现在有 3 颗糖。假设把额外的 3 颗全给他,总数就是 3 加 3 等于 6 颗。先把这个总数算出来,再去跟全场最大 5 比。
- 16拿 6 跟全场最大 5 比,6 不小于 5,说明他追平或超过了最多,result[1] 填 true,绿色点亮。
- 17轮到第 2 个孩子,他现在有 5 颗糖。假设把额外的 3 颗全给他,总数就是 5 加 3 等于 8 颗。先把这个总数算出来,再去跟全场最大 5 比。
- 18拿 8 跟全场最大 5 比,8 不小于 5,说明他追平或超过了最多,result[2] 填 true,绿色点亮。
- 19轮到第 3 个孩子,他现在有 1 颗糖。假设把额外的 3 颗全给他,总数就是 1 加 3 等于 4 颗。先把这个总数算出来,再去跟全场最大 5 比。
- 20拿 4 跟全场最大 5 比,4 比 5 还小,他够不到最多,result[3] 填 false,蓝色表示判过但不达标。
- 21轮到第 4 个孩子,他现在有 3 颗糖。假设把额外的 3 颗全给他,总数就是 3 加 3 等于 6 颗。先把这个总数算出来,再去跟全场最大 5 比。
- 22拿 6 跟全场最大 5 比,6 不小于 5,说明他追平或超过了最多,result[4] 填 true,绿色点亮。
- 23五个孩子都判完了,回看一遍:第 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],跟开头说的一字不差。整道题就是两遍扫描:一遍找最大,一遍逐个比。
⚠️ 容易写错的地方
✗ 错：比较写成严格大于 candies[i]+extra > mx
✓ 对：要用大于等于 ≥,因为允许并列最多
题目明说可以有多个孩子同时拥有最多。一个孩子只要拿到额外糖果后达到 mx 这个值就算最多,不需要严格超过。比如全场最大是 5,某孩子加完正好 5,他就是并列最多,该标 true;用严格大于会把这种并列误判成 false
✗ 错：在判定每个孩子时都重新扫一遍求最大
✓ 对：求最大只在循环外做一次,存进 mx 反复用
最大值是固定的,跟判定哪个孩子无关。如果每判一个孩子就重新 max 一次,等于把 O(n) 的求最大做了 n 遍,整体退化成 O(n²)。正确做法是先一次性求出 mx,第二遍直接拿来比
✗ 错：以为额外糖果给一个孩子后,别人的就变少了
✓ 对：每个孩子都是独立假设,额外糖果不会真的发掉
这份额外糖果是「假设全给他」来判断,判完下一个孩子时,这份额外糖果原封不动,还能再假设全给下一个。所以每个孩子都拿同一个 mx 来比,互不影响,不存在「发完就没了」
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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]C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
int mx = *max_element(candies.begin(), candies.end());
vector<bool> res;
for (int candy : candies) {
res.push_back(candy + extraCandies >= mx);
}
return res;
}
};Java
import java.util.*;
class Solution {
public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
int mx = 0;
for (int candy : candies) {
mx = Math.max(mx, candy);
}
List<Boolean> res = new ArrayList<>();
for (int candy : candies) {
res.add(candy + extraCandies >= mx);
}
return res;
}
}复杂度
时间
O(n)
n 是孩子个数。第一遍扫一遍 candies 求最大是 O(n),第二遍再扫一遍逐个判定也是 O(n),两遍相加仍是 O(n)。注意求最大要在循环外只做一次,千万别在判定每个孩子时都重新求一遍最大,那会退化成 O(n²)
空间
O(1)
按峰值算,除了必须交出去的长度为 n 的结果数组(这部分是输出,O(n)),额外只用了 mx 和循环变量这几个常数空间,所以辅助空间是 O(1)。Java 装布尔用的 ArrayList、C++ 的 vector 也都是承载输出的容器,不算额外增长
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 拥有最多糖果的孩子 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么时间复杂度是 O(n),能不能一遍扫完?+
因为先扫一遍求全场最大是 O(n),再扫一遍逐个判定也是 O(n),两遍相加还是线性。能不能一遍?不太行,因为判定每个孩子都要跟「全场」最大比,而全场最大得把整个数组看完才能确定,所以求最大必须先独立走完一遍。但要切记求最大只做这一次,别在判定循环里反复求,否则会变成 O(n²)。
比较为什么要用大于等于而不是严格大于?+
因为题目允许并列最多,可以有多个孩子同时拥有最多的糖果。一个孩子拿到额外糖果后,只要达到全场最大值就算「最多」,不需要严格超过别人。如果用严格大于,那些加完正好等于最大值的孩子会被误判成 false,结果就错了。尤其是本身就持有最大值的孩子,因为额外糖果至少有 1 颗,他加完一定大于原最大,所以一定是 true。
结果数组有没有可能全是 false?+
不可能。因为额外糖果 extraCandies 至少是 1,而原本就持有全场最大 mx 的那个孩子,加上额外糖果后会变成 mx 加 extraCandies,严格大于 mx,自然也不小于 mx,所以他一定是 true。也就是说答案里至少有一个 true,永远不会全 false。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 拥有最多糖果的孩子 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。