1. 糖果分配一道被低估的贪心入门题“糖果”这道题LeetCode 135很多OJ上也叫Candy是我觉得最适合检验贪心功底的题目之一。它没有复杂的排序没有花哨的数据结构只有两个看起来很简单的规则每个孩子至少分到1颗糖果评分比邻居高的孩子必须比邻居拿得多。问的是满足规则所需的最少糖果总数。听起来不难真正动手写的时候很多人会在“一次扫描里又想看左边又想看右边”的思路上卡很久最后发现顾此失彼。这篇我打算把这道题彻底讲透它为什么能套贪心算法“从左到右扫一遍、从右到左再扫一遍”这个经典解法为什么是对的、中间哪一步最容易写错还会把环形糖果、等分糖果这些变种问题一起梳理一遍。如果你正在备考面试或者刚开始刷贪心算法这篇应该能帮你省下不少绕弯的时间。文章后半段还会拿“跳跃游戏2”来做对比因为这两道题放在一起看比单独刷十道同类题更能理解贪心的边界。1.1 为什么“每个孩子尽量少拿”就是全局最优先拆规则。第一条规则是保底每个人都至少有1颗第二条规则是相对约束只发生在相邻两个孩子之间。注意约束是局部的一个孩子需要拿多少糖只取决于他和左右邻居的评分对比跟远处的孩子没有直接关系。既然是求总数最少一个很自然的想法就是在满足规则的前提下每个孩子都尽可能少拿。这里其实藏着贪心算法的核心逻辑——局部最优能不能推出全局最优对这道题来说是可以的。因为任何一个合法方案里如果某个孩子在满足规则的前提下还能再少拿1颗那么总数还能继续下降所以最优解里每个孩子一定都“紧贴”着约束边界要么被保底1颗卡住要么被邻居的糖果数卡住。这样一来从局部最小推到全局最小就站得住脚。这也解释了为什么“先把评分排序再从低分到高分发糖”是错的。排序只能告诉你谁高谁低但题目要求的是相邻关系一个高评分孩子可能夹在两个更高评分的孩子中间也可能站在边界上情况完全不同而且评分数组本身不是单调的波峰处需要同时满足左右两个方向的约束全局排序拿不到这些局部信息。1.2 最容易掉进去的直觉陷阱一次扫描两面兼顾很多人第一次写这题会想当然地用一个for循环从左往右扫每到一个位置就同时看一眼左边和右边然后直接定这个孩子的糖果数。这个思路表面合理实际一跑就出问题。举个反例ratings [1, 3, 2, 1]。一次扫描时第2个孩子评分3比左右都高你可能在扫描到他的时候就给他发3颗但等到扫描到第4个孩子时发现第3个孩子评分2比第4个孩子评分1高需要第3个孩子至少2颗而第2个孩子评分3又比第3个孩子高第2个孩子就得至少3颗。这个“连锁反应”会一路往后推前面的决策随时可能被后面的信息推翻。也就是说一次扫描里同时处理两个方向本质上是在用已经过时的信息做判断自然稳不住。更本质的原因是向右看的信息只有扫描到后面时才知道而向左看的信息却是确定的这两种信息到达的时间点不一样。所以正解不是在一个循环里同时处理两个方向而是把约束拆成两个方向分两次扫描分别处理。这个拆法就是贪心算法在这道题里的破题点。2. 把双向约束拆成“两个单向约束”问题就简单了一半题目里的约束都发生在相邻对上。对任意相邻对 (i, i1)只可能是三种关系之一评分左边高于右边、右边高于左边、两边相等。其中相等关系不会触发“必须更多”的规则所以真正需要处理的是前两种。这给了我一个很关键的启发把所有的相邻边按方向分成两组。“右边比左边高”的边只需要从左往右扫就能强制满足“左边比右边高”的边只需要从右往左扫就能强制满足。两次扫描各管一组等于是把一张二维的约束网拆成了两条一维的链。2.1 从左到右先保证“右边高就多拿”第一遍扫描只做一件事从左往右走如果发现 ratings[i] ratings[i-1]就把 candies[i] 设为 candies[i-1] 1否则不动。这一步结束之后所有“右边评分比左边高”的相邻边都已经满足了“右边比左边多拿”的规则。而评分相等或下降的边这一遍根本不关心先放着。这步操作的直觉可以理解为“顺着上坡路累加”每遇到一次评分抬升糖果数就跟着加1一旦评分不再抬升糖果数就回到保底值1。这样每个上升段的糖果数其实是按1、2、3、4连续递增的绝不会浪费。2.2 从右到左再补上“左边高就多拿”的方向第二遍扫描从右往左处理的是另一类边ratings[i] ratings[i1] 时需要保证 candies[i] candies[i1]。这里有个非常重要的细节更新要写成candies[i] max(candies[i], candies[i1] 1)而不是直接赋值为 candies[i1] 1。因为第一遍扫描可能已经给 candies[i] 发了一个更大的值直接赋值会把第一遍的成果抹掉。比如 [1, 3, 2] 这个例子第一遍结束后 candies 是 [1, 2, 1]第二遍扫描到 i1 时candies[1] 已经是2而 candies[2]1 也是2取max后保持不变如果直接赋值会错误地把第2个孩子的糖从2改成1反而不满足评分3比评分2高的约束。取max这个动作本质上是让两次贪心的结果“取并集”哪个方向要求的糖果多就按哪个方向来。这也是为什么最终每个波峰位置能拿到足够大的值——它同时接收了两个方向传来的约束。3. 两次遍历为什么是完备的很多人没讲透网上很多题解直接说“先从左到右再从右到左”但很少有人解释清楚第二遍从右到左更新的时候会不会把第一遍已经满足的约束又破坏掉如果会破坏那这个算法就不一定对。这一节我想把完备性证明写完整这也是面试官最喜欢追问的点。3.1 第一遍留下的结果第二遍为什么不会被“误伤”关键要看清第二遍更新的条件。右到左扫描时只有当 ratings[i] ratings[i1] 这个降序条件成立时才会更新 candies[i]而且更新的是相邻对里评分更高的那一个。也就是说第二遍只会给“评分更高”的孩子额外加糖绝不会给评分更低的孩子加糖。现在看任意一条相邻边 (i, i1)分两种情况如果 ratings[i] ratings[i1]这是升序边。第一遍扫描已经保证了 candies[i1] candies[i] 1。第二遍扫描时因为 ratings[i] 并不大于 ratings[i1]所以 candies[i] 不会被更新又因为扫描顺序是从右往左candies[i1] 已经定稿不会再变。这条边两端的值都不变之前的不等式自然一直成立。如果 ratings[i] ratings[i1]这是降序边。第二遍扫描到 i 时一定会检查这条边并通过 max 操作让 candies[i] candies[i1] 1所以最终一定满足约束。至于第二遍给某个“评分更高”的孩子加了糖会不会破坏他右边已经处理好的边不会。因为这条边本身是降序边右边孩子评分更低给左边高评分孩子加糖只会让他和右边低评分孩子的差距更大方向是对的。会不会影响他左边还没处理的边有可能左边如果也是降序边之后扫描到更左边时自然会继续加糖如果左边是升序边那更左边的孩子评分更低需要更多糖的不是他而是更右边这个刚被加糖的孩子——但升序边要求的是“右边 左边”他现在糖变多了反而更满足。所以说第二遍的每一个更新动作都在强化已经满足的约束同时为还没处理的左侧保留调整空间。3.2 从“路径长度”视角再理解一遍换一个更直观的角度。把评分数组画成折线图“上坡”和“下坡”其实对应着两种路径长度。一个波峰位置最终拿到的糖果数等于它左边最长连续下降段长度和右边最长连续下降段长度的较大者再加1一个波谷位置通常拿1颗。左到右扫描相当于统计了每个点相对左侧的“上坡路径长度”右到左扫描相当于统计每个点相对右侧的“上坡路径长度”max操作就取了两个方向下坡长度的最大值。这个视角也解释了为什么全递减序列 [5,4,3,2,1] 最终会得到 [5,4,3,2,1] 而不是 [1,1,1,1,1]——第一遍没给任何递增信号第二遍从右边一路把差值补回来形成了5、4、3、2、1的阶梯。而全递增序列 [1,2,3,4,5] 第一遍就形成了1、2、3、4、5第二遍没有任何降序边需要处理所以保持不变。4. 落地成代码实现细节与复杂度分析理论清楚了代码其实很短。我给一个标准的Python实现然后逐行拆一下注意事项。def candy(ratings): n len(ratings) if n 0: return 0 candies [1] * n # 第一遍从左到右处理“右边评分更高”的边 for i in range(1, n): if ratings[i] ratings[i - 1]: candies[i] candies[i - 1] 1 # 第二遍从右到左处理“左边评分更高”的边 for i in range(n - 2, -1, -1): if ratings[i] ratings[i 1]: candies[i] max(candies[i], candies[i 1] 1) return sum(candies)时间复杂度和空间复杂度都是 O(n)。n0 时直接返回0n1 时 candies[1]sum1天然正确。代码里最值得注意的就是第二遍的 max少写了它就是另一种错误答案。另外条件里一定用严格大于不能写成大于等于——评分相等的两个孩子不需要互相比较这是规则本身的要求。4.1 为什么“回退补糖”的写法不好还有一种常见的错误思路只用一次从左到右的扫描每当遇到下降趋势就回头把前面所有需要加糖的位置重新补一遍。比如这样# 错误示范理论可行但最坏情况是 O(n^2) def candy_with_rollback(ratings): n len(ratings) candies [1] * n for i in range(1, n): if ratings[i] ratings[i - 1]: candies[i] candies[i - 1] 1 elif ratings[i] ratings[i - 1]: j i while j 0 and ratings[j - 1] ratings[j] and candies[j - 1] candies[j]: candies[j - 1] candies[j] 1 j - 1 return sum(candies)这段代码在遇到严格递减序列 [5,4,3,2,1] 时会非常恐怖每走到一个新位置while循环都要一路回退到数组开头总操作次数是 123...(n-1)退化到 O(n^2)。n 小的时候看不出问题但面试时被问到复杂度就露馅了。回退写法的本质问题是“反复推翻前面的决策”相当于在同一个问题上做了很多次重复计算。而两次扫描的贪心写法每一遍都只做加法且不回退天然避免了重复劳动。这也是贪心算法和“试错法”最明显的分界线贪心做过的决定不再推翻。4.2 用校验函数给贪心结果上个保险刷题或者写代码验证的时候我习惯写一个很小的校验函数把任意输出丢进去检查是否合法def is_valid(ratings, candies): n len(ratings) if len(candies) ! n: return False for v in candies: if v 1: return False for i in range(n - 1): if ratings[i] ratings[i 1] and candies[i] candies[i 1]: return False if ratings[i] ratings[i 1] and candies[i] candies[i 1]: return False return True这个函数在调试随机数据时特别有用。贪心算法看起来简单但边界条件、等号处理、方向写反这一类问题很难靠肉眼发现用校验函数跑几百组随机数组基本能暴露所有隐藏bug。我在实际刷题时凡是能写出校验函数的问题都会顺手写一个省下大量试错时间。5. 扩展玩法环形糖果、相等评分、只求总数不求方案刷完基础版之后我建议把题目稍微改一改用来检验自己是不是真的理解了。下面这几个变体都是在面试或讨论中真实出现过的。5.1 环形糖果首尾相邻怎么处理如果孩子围成一圈规则变成评分高的必须比左右两个邻居都拿得多也就是第一条和最后一个孩子也算相邻。常见做法是先找到评分最低的那个孩子作为“断点”从断点处把环拆成链。因为这个断点的评分全场最低在最优解里他一定不会收到来自邻居的“需要更多”的压力所以断开后从它开始做两次遍历最后再单独检查环形首尾边即可。但这里有个坑如果环上存在多个评分相同且都是最低的孩子随便选一个最低点断开不是所有情况都安全因为两个最低点之间可能隔着高评分的长链。更稳妥的做法是断开之后再做一次首尾校验如果不满足就手动调整。这个变体考察的是“把环形结构转换成线性结构”的能力和很多环形数组题目的思路一致。5.2 评分相等时千万别写成大于等于我见过相当多的人在这道题上因为等号翻车。规则里只说评分更高的人要比邻居多没说评分相等时必须区分高低。所以评分相等的相邻孩子完全可以拿同样多的糖果甚至可以出现“左边评分等于右边但左边拿得更多”这种看起来不平衡但完全合法的状态。用测试用例 [1, 2, 2] 来说明。如果写成 ratings[i] ratings[i-1] 就加糖第一遍会得到 [1, 2, 3]第二遍再从右往左一处理结果可能变成 [1, 2, 3]总数6而正确结果应该是 [1, 2, 1]总数4。差别的原因就是第三个孩子虽然评分和第2个孩子一样但他不需要比第2个多只要比两边都多才需要加糖。边界条件上写严格大于还是大于等于决定了结果的正确性。5.3 只求总数和打印分配方案是一回事吗题目一般只问最少糖果总数没有要求输出具体方案。但实际上两次遍历过程中生成的 candies 数组本身就是一套满足规则的最小分配方案。所以打印方案和求总数不冲突直接 return sum(candies) 即可。有一点需要说明满足规则的最小分配方案不一定是唯一的。比如 [1, 2, 3, 2, 1]最优方案 [1, 2, 3, 2, 1] 基本是唯一的因为它被两侧边界压死了。但像 [1, 2, 1, 1] 这种场景可能还有别的合法方案只是总数会比最小方案大。题目要的是最小总数所以两次遍历生成的那套方案已经够了不需要额外考虑“方案不唯一”的干扰。6. 我踩过的坑与调试记录这一节把我在实际写这道题时踩过的坑集中整理一下有些坑是在LeetCode提交时被测试用例打脸才发现的有些是在帮别人 review 代码时看到的。6.1 全递减序列专门治“第二遍方向写反”第一次独立写这题时我把第二遍的 range 写成了 range(1, n)导致整个降序段没有任何补糖操作结果 [5,4,3,2,1] 返回5而不是15。后来我用全递减、全递增、先增后减、先减后增这四类基础样例作为自测用例才把方向问题彻底暴露出来。全递减序列是一个特别好的调试样例因为它直接检验第二遍扫描是否真的从右往左执行了。写代码的时候可以用笔在纸上模拟一下i 从 n-2 开始一路减到0每次检查 ratings[i] 是否大于 ratings[i1]。方向一旦写成从左往右这个序列就完全失效。6.2 波峰取值max 丢掉会错得莫名其妙我第一次提交错误版本时用的不是 max 而是直接赋值。有个测试用例是 [1, 3, 2, 4]第一遍得到 [1, 2, 1, 2]第二遍用直接赋值会变成 [1, 1, 1, 2]结果总数从6变成5。这个5明显不合法因为第2个孩子评分3比两边都高只拿1颗糖肯定不行。用 max 之后第二遍在 i1 处发现 candies[1] 已经是2和 candies[2]1 相等保持不变最终得到正确结果。所以第二遍不是“重新计算”而是“在现有基础上补齐缺失的约束”这一点在写代码时一定要体现在 max 上。6.3 边界条件的三个典型样例我给自己定的自测样例是这三组输入期望输出说明[]0空数组边界[1]1单元素边界[1,2,2]4等号不触发额外糖果前两个主要防数组越界第三个防大于等于误用。把这些样例和“全递减、全递增、波峰波谷交替”组合在一起基本上能把这道题的常见坑都覆盖一遍。6.4 用随机数据验证才是终极兜底固定样例跑得再多也不如随机验证来得安心。我写题时经常在本地用 for 循环生成几百组随机数组每组都同时跑“两次遍历版”和“校验函数”一旦发现 is_valid 返回 False 就立刻打印数组排查。这个方法帮我发现过一个非常隐蔽的问题当数组特别长时整数溢出虽然不太可能但逻辑上的细微错误确实会被随机数据放大。7. 同源贪心题串讲从跳跃游戏2看贪心家族的共性热搜词里经常把“糖果”和“跳跃游戏2”放在一起讨论我猜是因为这两道题都贴着贪心的标签但表现形态差异很大放在一起对比反而收获更多。7.1 跳跃游戏2的核心贪心策略跳跃游戏2的问题是给定一个非负整数数组每个位置的数字表示你最多可以往后跳的距离问从第0个位置跳到最后一个位置最少需要几步。贪心解法不关注“具体跳哪个位置”而是维护两个边界当前步数能到达的最远位置 curEnd以及从当前区间内出发能够到达的更远位置 far。每遍历到一个位置就更新 far当 i 到达 curEnd 时说明这一跳已经用尽步数加1并把 curEnd 更新为 far。def jump(nums): n len(nums) if n 1: return 0 step 0 cur_end 0 far 0 for i in range(n - 1): far max(far, i nums[i]) if i cur_end: step 1 cur_end far if cur_end n - 1: break return step这个做法的贪心体现在每一步都选择“下一步能到达更远位置”的方案而不是选择“当前跳得最远”的位置。前一种策略在数学上可以证明是最优的因为有交换论证支持如果最优解里某一步跳到了一个更近的位置用它换成当前区间内能跳到最远位置的方案后续能覆盖的范围只会更大不会更差。7.2 糖果和跳跃游戏2到底有哪些共性我把两道题的贪心结构放在一起看对比维度糖果跳跃游戏2约束类型相邻位置的相对大小当前位置的可达范围贪心动作只在评分更高时多发1颗糖只在边界处扩展最远可达范围是否有回退没有第二遍只增不减没有每次只更新 far核心证明第二遍更新不会破坏第一遍结果选择最远点不会缩小可达范围时间复杂度O(n)O(n)两个问题的共同点在于局部最优决策都具有“无后效性”。糖果问题里第一遍只处理升序边第二遍只处理降序边两个方向的决策互不干扰跳跃游戏2里每次选择能跳更远的点后续决策仍然只依赖“最远能到哪”而不依赖之前具体跳到了哪个位置。正是因为无后效性贪心才能少做很多无用功。7.3 怎么判断一道题能不能用贪心这个问题经常被问我的经验是分三步走。第一步看题目能不能分成“每到一个状态做一次局部决策”的结构第二步尝试构造反例看局部最优是否会破坏全局最优第三步如果能用交换论证或单调性说明局部最优不会让全局变差那贪心就成立否则大概率要用动态规划。糖果问题恰好是一个非常典型的案例如果你试图在一个循环里同时满足两个方向局部决策就会因为后续信息的介入而失效拆成两个方向之后每个方向的局部决策都是安全的。这也是为什么它适合作为贪心的入门题——它让你直观感受到“决策的顺序”和“信息到达顺序”之间的关系。我自己现在做贪心题第一反应已经不是背套路而是先画一下约束的方向哪些信息从左到右能确定哪些信息从右到左才能确定哪些信息必须保留到最后。把方向理清楚糖果、跳跃游戏2、加油站、分发饼干这些题目其实都是同一套思考路径下的不同变体。