LeetCode 1431 拥有最多糖果的孩子：从数组遍历到贪心思想

我是那种喜欢把简单题也拆开看的人。LeetCode 1431“拥有最多糖果的孩子”看起来简单到有点“不值得写”但当我提交之后看到耗时100ms这个数字时反而停下来多想了想一个只需要遍历数组一遍的题为什么不同人写出来耗时差别这么大是语言差异、容器选择、还是一些我自己都没注意到的分支判断如果你也刷过这道题大概会有同感——“太简单了没啥好写”其实是一种错觉。这道题背后涉及的是对数组操作的基本功、边界处理意识以及对复杂度分析的理解方式。这篇文章把它完整记录下来适合刚开始刷题的朋友照着练手也适合老手回头看看自己是不是在某些细节上还能抠出一点优化空间。1. 题目到底在问什么——先别急着写代码把“最多”两个字拆清楚1.1 原题场景还原题目设定很生活化有一群孩子每个孩子手里有若干颗糖果。现在你手里有一把额外的糖果可以全部给某一个孩子。问题是对于每一个孩子来说如果把额外的糖果都给他他能不能成为糖果最多的那位。对应到代码上就是一个数组candies数组里每个元素是一个孩子当前的糖果数。再给一个整数extraCandies表示额外糖果的数量。输出一个布尔数组第i个元素代表如果把额外糖果全给第i个孩子他手里的糖果数量是否能大于等于原数组中的最大值。很多人在这一步没问题但会在一个细节上栽跟头——“最多的孩子”到底允不允许并列。题目原话是“greatest number of candies”判断条件用的是大于等于而不是严格大于。也就是说如果这个孩子加上额外糖果后和其他孩子并列第一他也算满足条件。从英文题面看就是candies[i] extraCandies maxCandies这个细节直接决定比较符号是还是写错就是一次 WA。1.2 为什么这道题属于“逻辑简单但容易讲不清”的类型我见过不少人在讨论区里贴代码思路是“先复制一份数组每个元素加完额外糖果后再和原数组的每个元素比较一遍”。这个做法当然也能得到正确答案但时间复杂度会变成 O(n^2)完全没必要。问题的本质其实是两个步骤第一步找到这群孩子里当前糖果数量的上限也就是最大值第二步逐个判断每个孩子加上额外糖果后能不能触到这个上限。这里可以做一个生活化类比想象一群小朋友排队做游戏游戏规则是“谁手里的糖果最多谁当队长”。你现在有一把额外的糖果可以一次性全塞给其中的某个小朋友你要依次问每个小朋友如果把额外糖果都给你你手里的糖果数能不能达到现在队伍里的最高纪录。核心就在于最高纪录只需要先量一次而不是每次比较时都重新量一遍。这个拆解看起来简单但它其实是很多“双指针”“前缀和”类问题的雏形先预处理出一个全局信息比如最大值、前缀和、哈希映射再基于这个信息做单次遍历判断。1431这道题虽然用不着那么复杂的数据结构但它能帮你建立“先全局后局部”的思维习惯。2. 最直接的解法——一遍找最大值一遍做判断完事2.1 为什么必须先找出最大值如果你把数组里每个元素都加上extraCandies然后判断它是不是最大的存在一个循环依赖判断“是不是最大”需要一个参照物而这个参照物如果也在变化那就没法比较了。所以必须先固定参照物也就是原始数组的最大值。有一种常见误解是可以先把所有元素都加上extraCandies然后取新数组的最大值再一个个比较。这在数学上等价于“每个孩子都拿到额外糖果后再比谁最多”但和题目语义不符。题目说的是额外糖果只能给一个孩子不是每个人都能得到。所以正确参照物必须是原始最大值一旦加完再取最大值参照物就被污染了。2.2 实现代码与运行流程先给一个最常规的 C 写法class Solution { public: vectorbool kidsWithCandies(vectorint candies, int extraCandies) { int maxCandies 0; for (int c : candies) { maxCandies max(maxCandies, c); } vectorbool result; result.reserve(candies.size()); for (int c : candies) { result.push_back(c extraCandies maxCandies); } return result; } };流程很清晰第一个循环找到最大值第二个循环逐个判断把布尔值存进结果数组。整个过程只遍历了两遍数组时间复杂度 O(n)额外空间除了结果数组外只有几个变量空间复杂度 O(1)如果把结果数组算上则是 O(n)。再看 Python 版本这个版本在 LeetCode 上很常见class Solution: def kidsWithCandies(self, candies: List[int], extraCandies: int) - List[bool]: max_candies max(candies) return [c extraCandies max_candies for c in candies]Python 的max()内部是用 C 实现的列表推导式的循环也在 CPython 的字节码层面做了不少优化所以写起来非常简洁。但简洁归简洁如果不理解max(candies)这一步是在干什么面试时一旦被追问就很容易露馅。2.3 复杂度分析O(n) 到底是怎么来的第一遍遍历数组找最大值需要比较 n-1 次第二遍遍历数组做判断需要 n 次比较。总的比较次数约为 2n在渐进意义上就是 O(n)。空间上结果数组长度为 n每个元素是一个布尔值因此额外空间是 O(n)但这个空间本来就是题目要求输出的属于“不可避免”的空间。有人会问能不能只遍历一遍就完成理论上如果你事先知道最大值当然可以但在不知道最大值的情况下你必须先完整看过数组才能确定最大值。除非数组有序或者题目给了额外信息否则这个“先找最大值”的步骤省不掉。这也是为什么这道题的最优时间复杂度就是 O(n)。3. “耗时100”背后——同一个题为什么不同人写出来耗时差好几倍3.1 提交记录里的耗时数字到底说明了什么先泼一盆冷水LeetCode 上显示的耗时是一个很粗糙的指标受服务器负载、语言版本、测试用例顺序、甚至提交时间的影响都很大。同一份代码连续提交两次耗时可能差 20ms。所以“耗时100ms”本身不说明代码好或者不好但它可以作为一个引子去思考代码里有哪些影响实际运行速度的地方。在我提交这道题的时候C 版本的耗时大概在 100ms 上下波动。这个数字对一道 O(n) 的简单题来说属于正常范围因为测试用例里数组长度最大是 100这个量级本身就很小耗时主要花在函数调用、容器分配和结果返回上而不是真正的比较逻辑上。3.2 影响耗时的几个真实因素第一个因素是容器的选择。如果结果用vectorbool要注意vectorbool是一个特化版本它为了节省空间把每个布尔值压缩成一个比特位而不是一个完整的bool对象。这就导致读写vectorbool里的元素时编译器需要做位运算反而比普通vectorchar更慢。在 n 很小的时候差距不明显但如果以后遇到大数据量的布尔数组这个特性就值得注意了。第二个因素是内存分配的次数。如果你在循环里反复push_back而且没有提前reserve容器会多次扩容、搬移元素这在 n 大时很伤性能。我在 C 代码里写了result.reserve(candies.size())就是为了避免这个不必要的开销。对于 n100 的用例来说可能无所谓但这是一个好习惯。第三个因素是分支预测。判断条件c extraCandies maxCandies的结果在数组中的分布是不确定的这会导致 CPU 分支预测器时而猜对时而猜错。但这里只有一个分支没有复杂的if-else嵌套所以影响很小。3.3 在简单题里值得做的微优化清单我把这道题能想到的微优化列成一张表供参考优化点做法效果提前分配结果空间result.reserve(candies.size())避免多次扩容搬移用引用避免拷贝for (int c : candies)改成const int c尤其是元素为大对象时减少拷贝开销合并两次遍历先找最大值本身就必须遍历一次无法合并无使用局部变量存储高频值把candies.size()存入局部变量防止每次循环重新读取避免在循环里调用函数push_back可以换成下标赋值前提是已 resize减少函数调用开销说实话对 n100 的用例来说上面这些优化加起来可能也就影响几毫秒。但刷题的意义不只是过这道题而是把这些习惯内化以后遇到 n10^5、10^6 的数据时才不会临时手忙脚乱。4. 边界条件与易错点——简单题也有翻车的地方4.1 当每个孩子原本都是最大值时如果数组是[5, 5, 5]extraCandies 0那么每个孩子加 0 后还是 5都满足最大值 5所以结果应该是[true, true, true]。这里只要用了就不会错但如果你在代码里写的是c extraCandies maxCandies那么三个孩子全部返回false直接和题意相悖。这个坑很浅但踩到的人不少因为现实语言里“最多”往往让人下意识认为必须是严格大于。4.2 额外的糖果为 0 时当extraCandies 0时题目退化成“每个孩子是否已经是最大值”。这时候结果数组里只有原本等于最大值的那些孩子是true。逻辑不需要特判天然就能处理。但如果你在代码里额外写了一个if (extraCandies 0)之类的分支那就要检查分支内的逻辑是否和常规逻辑一致否则容易多此一举写出 bug。4.3 数组长度与数值范围题目给的数据范围是candies.length在 2 到 100 之间candies[i]在 1 到 100 之间extraCandies在 1 到 50 之间。因此c extraCandies最大是 150完全不会溢出int。但如果是自己扩展这道题把数值范围放大到 10^9 甚至更大就要考虑用long long来避免加法溢出。这个意识很重要很多人在简单题里不检查溢出到了大数题里就吃亏。还有一个隐藏细节数组长度最小是 2所以不需要担心空数组的情况。但如果你把代码当作通用工具函数来写最好还是加上空数组保护返回空结果即可。多写一行防御代码不丢人。5. 从这道题延伸出去——和贪心、统计思想的连接5.1 为什么这道题可以算是贪心思想的入门贪心思想的核心是“在每一步做出当前看起来最优的选择希望最终达到全局最优”。在这道题里每个孩子只有两种选择拿到额外糖果或拿不到。判断他拿到额外糖果后能不能成为最大值其实就是在做一次局部最优判断把全部额外糖果都给他是让他达到“最多”这条线的最直接手段。如果你把额外糖果拆成一小份一小份分别给不同孩子那道题就会变成另一个更复杂的分配问题。但题目明确说“all of the extra candies”可以全部给一个孩子这个“全部给一个”的设计正好让问题退化成简单的最大值比较。以后你做“发糖果”“分任务”这类题时如果题目里也出现“可以把所有资源集中给一个对象”的条件大概率就是在暗示你用贪心或者直接比较的思路。5.2 类似题目的举一反三LeetCode 上有很多题和 1431 共享同一个“先求全局参照再逐元素验证”的骨架。比如判断一个数组里每个元素与最大值的差距可以用类似逻辑。找出数组中满足某个累计条件的最小索引/最大索引常常需要先预处理前缀和。如果题目变成“哪些孩子加上额外糖果后糖果数能超过某个阈值”那只要把maxCandies换成阈值即可。我刷题时的习惯是每做完一道简单题就问自己三个问题。第一这题能不能改造成更复杂的版本第二如果面试官要求只遍历一遍怎么办第三如果数据量变成 10^7现有解法还顶不顶得住带着这三个问题去看 1431答案分别是可以改成“给每个孩子不同的额外糖果”的分配问题只遍历一遍做不到需要额外信息O(n) 的解法在 10^7 量级下也完全没问题但要留意语言层面的常数优化。5.3 面试官会顺着这道题追问什么如果这是面试中的热身题面试官常见的追问方向有三个。第一个是“能不能不用额外数组返回结果”答案是可以直接修改原数组用原数组存布尔结果但要注意类型不匹配一般还是建议新建结果数组。第二个是“如果额外的糖果数量很大大到每个孩子都能成最大值你的代码会怎样表现”这其实是在问边界答案是逻辑天然处理不会有问题。第三个是“你的解法时间复杂度为什么是 O(n)有没有可能达到 O(log n)”这就涉及到信息论了只看数组前几个元素无法确定最大值所以在最坏情况下不可能少于 O(n) 的比较次数。这里我想多说一句面试时的简单题考察的往往不是你能不能写出来而是你能不能把自己的思考过程讲出层次。“先找最大值这一步是在干什么”这个问题如果你能回答出“固定参照物、避免循环依赖”那么在面试官心里的印象会好很多。6. 最后再分享一点实际体会我自己在重新做这道题的时候最大的感悟是简单题是培养代码习惯最好的试验场。因为没有复杂的算法干扰你可以把注意力集中在变量命名、边界处理、常数优化这些平时容易忽略的地方。我的建议是不要一看到简单题就直接秒写然后提交而是先想一想如果这道题的数据范围扩大一万倍现在这个写法还能不能跑得动。如果答案是否定的那你就有优化空间了。另外关于“耗时100”这个记录我想说的是不要过分纠结于 LeetCode 的计时器。真正值得关心的是你自己能不能在写代码之前把逻辑讲清楚写完之后能不能说出每一行的目的。这道题你能写出 O(n) 的解法不难难的是以后遇到“找参照物再遍历”的问题模式时能第一时间反应过来。刷题数量不是目的把这个模式吃进脑子里才是。如果让我给一个扩展练习的方向我会建议你把这道题的判断条件改成“加上额外糖果后是否能成为唯一最多”也就是严格大于最大值然后想想结果会有什么不同。再到 LeetCode 上找一道“模拟分组”的题看看同样的先全局后局部思想是怎么被用在更复杂场景里的。这样反复练几次1431 这道题才算真正被你吃透了。