糖果分配问题：贪心算法双向遍历的经典入门

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, i+1)，只可能是三种关系之一：评分左边高于右边、右边高于左边、两边相等。其中相等关系不会触发“必须更多”的规则，所以真正需要处理的是前两种。

这给了我一个很关键的启发：把所有的相邻边按方向分成两组。“右边比左边高”的边，只需要从左往右扫就能强制满足；“左边比右边高”的边，只需要从右往左扫就能强制满足。两次扫描各管一组，等于是把一张二维的约束网拆成了两条一维的链。

2.1 从左到右：先保证“右边高就多拿”

第一遍扫描只做一件事：从左往右走，如果发现 ratings[i] > ratings[i-1]，就把 candies[i] 设为 candies[i-1] + 1；否则不动。这一步结束之后，所有“右边评分比左边高”的相邻边，都已经满足了“右边比左边多拿”的规则。而评分相等或下降的边，这一遍根本不关心，先放着。

这步操作的直觉可以理解为“顺着上坡路累加”：每遇到一次评分抬升，糖果数就跟着加1；一旦评分不再抬升，糖果数就回到保底值1。这样每个上升段的糖果数其实是按1、2、3、4连续递增的，绝不会浪费。

2.2 从右到左：再补上“左边高就多拿”的方向

第二遍扫描从右往左，处理的是另一类边：ratings[i] > ratings[i+1] 时，需要保证 candies[i] > candies[i+1]。这里有个非常重要的细节，更新要写成：

candies[i] = max(candies[i], candies[i+1] + 1)

而不是直接赋值为 candies[i+1] + 1。因为第一遍扫描可能已经给 candies[i] 发了一个更大的值，直接赋值会把第一遍的成果抹掉。比如 [1, 3, 2] 这个例子，第一遍结束后 candies 是 [1, 2, 1]，第二遍扫描到 i=1 时，candies[1] 已经是2，而 candies[2]+1 也是2，取max后保持不变；如果直接赋值，会错误地把第2个孩子的糖从2改成1，反而不满足评分3比评分2高的约束。

取max这个动作，本质上是让两次贪心的结果“取并集”：哪个方向要求的糖果多，就按哪个方向来。这也是为什么最终每个波峰位置能拿到足够大的值——它同时接收了两个方向传来的约束。

3. 两次遍历为什么是完备的？很多人没讲透

网上很多题解直接说“先从左到右，再从右到左”，但很少有人解释清楚：第二遍从右到左更新的时候，会不会把第一遍已经满足的约束又破坏掉？如果会破坏，那这个算法就不一定对。这一节我想把完备性证明写完整，这也是面试官最喜欢追问的点。

3.1 第一遍留下的结果，第二遍为什么不会被“误伤”

关键要看清第二遍更新的条件。右到左扫描时，只有当 ratings[i] > ratings[i+1] 这个降序条件成立时，才会更新 candies[i]，而且更新的是相邻对里评分更高的那一个。也就是说，第二遍只会给“评分更高”的孩子额外加糖，绝不会给评分更低的孩子加糖。

现在看任意一条相邻边 (i, i+1)，分两种情况：

• 如果 ratings[i] < ratings[i+1]，这是升序边。第一遍扫描已经保证了 candies[i+1] >= candies[i] + 1。第二遍扫描时，因为 ratings[i] 并不大于 ratings[i+1]，所以 candies[i] 不会被更新；又因为扫描顺序是从右往左，candies[i+1] 已经定稿，不会再变。这条边两端的值都不变，之前的不等式自然一直成立。
• 如果 ratings[i] > ratings[i+1]，这是降序边。第二遍扫描到 i 时一定会检查这条边，并通过 max 操作让 candies[i] >= candies[i+1] + 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)。n=0 时直接返回0；n=1 时 candies=[1]，sum=1，天然正确。代码里最值得注意的就是第二遍的 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循环都要一路回退到数组开头，总操作次数是 1+2+3+...+(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[i+1]。方向一旦写成从左往右，这个序列就完全失效。

6.2 波峰取值：max 丢掉会错得莫名其妙

我第一次提交错误版本时，用的不是 max 而是直接赋值。有个测试用例是 [1, 3, 2, 4]，第一遍得到 [1, 2, 1, 2]，第二遍用直接赋值会变成 [1, 1, 1, 2]，结果总数从6变成5。这个5明显不合法，因为第2个孩子评分3比两边都高，只拿1颗糖肯定不行。

用 max 之后，第二遍在 i=1 处发现 candies[1] 已经是2，和 candies[2]+1 相等，保持不变，最终得到正确结果。所以第二遍不是“重新计算”，而是“在现有基础上补齐缺失的约束”，这一点在写代码时一定要体现在 max 上。

6.3 边界条件的三个典型样例

我给自己定的自测样例是这三组：

前两个主要防数组越界，第三个防大于等于误用。把这些样例和“全递减、全递增、波峰波谷交替”组合在一起，基本上能把这道题的常见坑都覆盖一遍。

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里，每次选择能跳更远的点，后续决策仍然只依赖“最远能到哪”，而不依赖之前具体跳到了哪个位置。正是因为无后效性，贪心才能少做很多无用功。

7.3 怎么判断一道题能不能用贪心

这个问题经常被问，我的经验是分三步走。第一步，看题目能不能分成“每到一个状态做一次局部决策”的结构；第二步，尝试构造反例，看局部最优是否会破坏全局最优；第三步，如果能用交换论证或单调性说明局部最优不会让全局变差，那贪心就成立，否则大概率要用动态规划。

糖果问题恰好是一个非常典型的案例：如果你试图在一个循环里同时满足两个方向，局部决策就会因为后续信息的介入而失效；拆成两个方向之后，每个方向的局部决策都是安全的。这也是为什么它适合作为贪心的入门题——它让你直观感受到“决策的顺序”和“信息到达顺序”之间的关系。

我自己现在做贪心题，第一反应已经不是背套路，而是先画一下约束的方向：哪些信息从左到右能确定，哪些信息从右到左才能确定，哪些信息必须保留到最后。把方向理清楚，糖果、跳跃游戏2、加油站、分发饼干这些题目，其实都是同一套思考路径下的不同变体。