做算法题的人应该都见过这道“糖果”题一群孩子站成一排每个孩子有一个评分你要按两条规则发糖果问最少准备多少颗。它在 LeetCode 上的编号是 135难度标着 Hard很多题单把它和“跳跃游戏2 贪心算法”这类题放在一起作为贪心思想的进阶训练。我第一次做的时候没有直接想贪心而是试图用差分、模拟之类的思路硬推结果被“相邻关系互相牵扯”这件事卡了很久。后来才想明白这道题的正确打开方式就是贪心而且是那种“把问题拆成两个方向分别贪心”的典型结构。这篇文章我会从题目本身一步步拆起讲清楚为什么贪心在这里能成立、两次遍历到底在干什么、代码怎么写再把常见的坑和容易混淆的边界条件全部过一遍。最后会把糖果问题和跳跃游戏2、分发饼干这类经典贪心题放在一起做对比帮你看清贪心题的共同套路。不管你是准备面试还是单纯想搞懂这个 Hard 题这篇文章都值得完整看一遍。先交代一下这道题适合谁如果你是刚接触贪心算法的初学者建议先把分发饼干、跳跃游戏这类基础题刷完再看如果你已经刷过一部分题但对“为什么这个局部最优能推出全局最优”这件事总是说不清这道题正好是一面很好的镜子。1. 先把题目拆明白糖果分配背后的三条硬规则1.1 原题到底在说什么原题给了一个整数数组ratings长度是n代表n个孩子站成一排的评分。你需要给每个孩子分配糖果最后返回“最少需要准备多少颗糖果”。分配时只服从两条硬规矩每个孩子至少分到 1 颗糖果相邻两个孩子里评分更高的那个必须拿到更多糖果。注意这里说的是“相邻”的孩子之间比较不是全局比较。也就是说一个评分很低的孩子只要他的邻居评分比他更低他就可能拿到很多糖果评分最高的孩子也不一定是全场糖果最多的一切只看局部相邻关系。这里有一个很容易被忽视的点如果相邻两个孩子的评分相等题目没有要求他们拿一样多只要求两人都至少拿到 1 颗。也就是说评分相等时可以一个拿 5 颗另一个拿 1 颗只要不违反“评分高的人拿更多”这条规则就行。这个边界条件在写代码时特别容易出问题后面我会专门讲。1.2 为什么这道题难相邻约束的“环状依赖”我一开始想当然地觉得这题不就是从左到右扫一遍遇到评分上升就加一颗吗试了一下才发现不对。举个最简单的例子ratings [1, 3, 2]。如果只从左往右扫你会得到[1, 2, 1]总数是 4。但仔细检查ratings[2] 2比ratings[1] 3低确实不用比ratings[1]多所以这个结果是合法的总数也是对的。但如果换成ratings [1, 3, 2, 1]从左往右扫会得到[1, 2, 1, 1]。这时候你发现ratings[2] 2比ratings[3] 1高但candies[2] 1并不比candies[3] 1多违反了第二条规则。这就是问题的核心难处从左边看是斜坡从右边看可能也是斜坡你要同时满足两边的要求不能一个方向扫完就完事。这种“既要管左边邻居又要管右边邻居”的约束会形成一种类似环状依赖的结构。你想在某个孩子身上一次性满足两个方向就不得不反复调整已经分配好的糖果复杂度很容易飙升。1.3 一位从业者的直觉把规则拆成两个独立方向后来我看题解才意识到正确的拆法是把“同时满足左右两边”这个大问题拆成“每个孩子只考虑左边邻居”和“每个孩子只考虑右边邻居”两个子问题各自单独解决最后再把两个子问题的结果合并。听起来有点抽象但你可以把问题想象成两个方向的“比赛”从左往右看如果当前孩子比左边邻居评分高那他在左边这场“比赛”里必须比左边邻居拿得多。从右往左看如果当前孩子比右边邻居评分高那他在右边这场“比赛”里必须比右边邻居拿得多。一个孩子要同时赢下两场比赛他的最终糖果数就得取两场比赛要求里的最大值。这个“取最大值”的思路就是糖果问题的核心也是最难想明白但想明白之后就再也忘不掉的地方。2. 为什么贪心在这里能拿最优解从“相邻比较”到“两次遍历”2.1 贪心策略的直觉每次只给“最小必要量”贪心算法的核心是“局部最优能推出全局最优”。放在糖果问题里具体来说就是每次给一个孩子发糖果时我只给他“满足当前已知约束的最小数量”绝不多给。为什么这么做能保证最后总数量最少因为所有糖果的数量最终都是靠“至少 1 颗”和“相邻比较”这两条约束推出来的而这两条约束都是“最小值不等式”没有“精确相等”的要求。所以只要每个孩子在所有已经确定的约束下都拿的是最小值那么总数量一定是最小值。这一点是贪心能成立的根本原因也是后面所有推导的基础。2.2 第一次遍历从左向右只处理“右边更高”的情况第一步初始化一个数组candies让每个孩子先拿 1 颗。然后从左往右遍历如果ratings[i] ratings[i-1]说明当前孩子比左边邻居评分高那么candies[i] candies[i-1] 1否则candies[i]保持 1 不变。这样一轮下来数组里每个位置相对于左邻居的关系就都满足规则了。注意这个过程中我们只看“左边”完全不看“右边”所以这是第一个独立的贪心方向。这里有一个很值得品味的细节为什么是candies[i-1] 1因为左边邻居的值可能不是 1而是 1、2、3 这样一路加上来的。当前孩子只需要比左边邻居多 1 颗就可以在“左边高”这条规则下达到最小必要量。贪心在这里的体现就是“只加刚好够用的那一颗”。2.3 第二次遍历从右向左回补“左侧更高”的情况同时不破坏第一轮结果第一轮结束后右边邻居的关系可能还没满足比如ratings[i-1] ratings[i]的时候candies[i-1]不一定要比candies[i]多。现在从右往左再来一遍如果ratings[i] ratings[i1]说明当前孩子比右边邻居评分高那么candies[i] max(candies[i], candies[i1] 1)否则不做修改。这里的max是整道题最关键的环节。因为candies[i]已经在第一轮得到一个值这个值满足“左边关系”。如果直接覆盖成candies[i1] 1可能会把第一轮已经满足的左边关系破坏掉。取最大值的意思是既要满足右边关系的要求又不能丢掉左边关系已有的结果两边都要保住。这就是“拆成两个方向分别贪心再合并取最大”的核心逻辑。第一轮保证“每个孩子都有至少比左边邻居多 1 的底子”第二轮保证“每个孩子都有至少比右边邻居多 1 的底子”最终每个孩子拿的是两个底子中更大的那个两边规则就同时满足了。2.4 为什么两次贪心加在一起就是全局最优直观证明很多人可能会问你第一轮给了一些值第二轮用max去调整调整完以后左边的关系确定还能保住吗答案是能因为第二轮只会把candies[i]变大不会把它变小。在第一轮里candies[i]大于等于candies[i-1] 1的性质在数值变大之后依然成立。所以第二轮不会破坏第一轮已经满足的约束只会加上新的约束。这里其实是一个典型的“约束合并”思维整个问题由两个独立的约束体系组成每个体系各自构成一个“单调链”。贪心在每条链上都能找到满足该链的最小分配最后把两条链的分配逐点取最大值就得到同时满足两条链的最小分配。这个结论可以用反证法想如果最终某个孩子还能少拿一颗而不违反任何规则那么在至少一条链上他原本的取值就不是这条链上的最小必要值这与每一轮贪心的定义矛盾。所以糖果问题的“贪心正确性”并不是玄学而是由约束的“可拆分性”和“取 max 不破坏旧约束”这两件事共同保证的。3. 代码落地一次像样的实现长什么样3.1 基础版O(n) 时间 O(n) 空间先给出最直观、最适合面试时手写的 Python 实现def candy(ratings): n len(ratings) if n 0: return 0 # 每个孩子至少 1 颗 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)代码非常短但每一行都有讲究。candies [1] * n是把“至少 1 颗”这条规则直接做进了初始化第一轮覆盖“左边更高”第二轮用max合并“右边更高”最后求和就是最少糖果数。如果你用 Java 写逻辑完全一样只是语法区别public int candy(int[] ratings) { int n ratings.length; int[] candies new int[n]; Arrays.fill(candies, 1); for (int i 1; i n; i) { if (ratings[i] ratings[i - 1]) { candies[i] candies[i - 1] 1; } } for (int i n - 2; i 0; i--) { if (ratings[i] ratings[i 1]) { candies[i] Math.max(candies[i], candies[i 1] 1); } } int total 0; for (int c : candies) { total c; } return total; }3.2 代码里的关键细节初始化、边界和 max 的含义有几个容易写错的地方我单独拎出来说。第一个是初始化。很多新手拿到题目会先把candies数组初始化为 0然后在遍历里用candies[i - 1] 1来赋值。这样在第一次遇到“下降”情况时不加处理candies[i]就会是 0最后总和显然偏小。正确做法是初始化为 1因为“每个孩子至少 1 颗”是硬约束不是可选项。第二个是第二轮遍历的方向。必须从i n - 2往i 0走也就是从右往左。因为我们要用当前孩子的右边邻居更新当前孩子必须保证右边邻居已经被更新过。如果你一不小心把第二轮的循环写成了从左到右那candies[i 1]可能还是第一轮的值甚至初始值整个回补逻辑就失效了。第三个是第二轮的max不能省。有人会想既然第二轮要满足右边关系直接candies[i] candies[i 1] 1不就行了这会在类似ratings [1, 3, 2]这样的测试用例上出错。我们来验证一下第一轮过后candies [1, 2, 1]第二轮时i 1ratings[1] 3 ratings[2] 2如果直接赋值candies[1] candies[2] 1 2看起来没问题。但换成ratings [1, 3, 3, 2]第一轮结束后candies [1, 2, 1, 1]第二轮时i 2ratings[2] 3 ratings[3] 2直接赋值会让candies[2] candies[3] 1 2但此时candies[2]和candies[1]因为评分相等不需要比candies[1]多。看起来也对但如果评分是[1, 3, 4, 3]第一轮后candies [1, 2, 3, 1]第二轮时i 2ratings[2] 4 ratings[3] 3直接赋值会得到 2结果candies[1] 2的左边关系要求candies[2]至少是 3于是被破坏了。必须取max(3, 2) 3才能两边都保住。3.3 进阶思考空间能不能降到 O(1)基础版的时间复杂度是 O(n)空间复杂度是 O(n)因为开了一个长度n的数组。如果面试官追问能不能优化空间还有一个 O(1) 空间的版本思路是把数组换成“上升段、下降段”的统计。核心逻辑是从左往右扫一遍记录当前处于上升段还是下降段。上升段时当前孩子糖果数比上一个多 1直接累加下降段时当前孩子糖果数从 1 开始递增累加时还要考虑峰值位置是否已经被上升段记录过。这个版本的细节比较多这里给一个参考实现def candy_o1(ratings): n len(ratings) if n 0: return 0 total 1 up 0 down 0 peak 0 for i in range(1, n): if ratings[i] ratings[i - 1]: up 1 down 0 peak up total 1 up elif ratings[i] ratings[i - 1]: up 0 down 0 peak 0 total 1 else: down 1 up 0 total 1 down if peak down: total - 1 return total这个版本的核心是peak变量它记录上升段最高点已经累计到的糖果数。当下降段长度还没超过峰值时下降段的起点也就是峰值点不需要因为下降而额外增加糖果所以累加1 down之后要减掉多算的 1。当下降段长度超过峰值后峰值点需要额外补一颗这个修正就不再执行。我的建议是面试时先写出 O(n) 空间的版本保证逻辑清晰和正确性。O(1) 版本可以作为加分项但背代码前一定要把peak的修正逻辑理解透否则现场很容易写错。4. 实战中的高频雷区与排查思路4.1 雷区一两个方向的遍历顺序搞反这是最隐蔽的错误。第一轮必须是“从左到右”第二轮必须是“从右到左”顺序反了会导致结果不正确。原因在于第一轮要利用左边的信息只能从左往右递推第二轮要利用右边的信息只能从右往左递推。如果你第一轮写成从右到左那candies[i - 1]还没被更新过比较就没有意义。排查技巧用一个单调递增的测试用例比如ratings [1, 2, 3, 4, 5]如果你的实现得到不是[1, 2, 3, 4, 5]的分配说明第一轮方向有问题。再用单调递减的用例ratings [5, 4, 3, 2, 1]检查第二轮。4.2 雷区二所有孩子的初始值设成了 0我之前见过有人把candies初始化为 0然后从第二个孩子开始用candies[i] candies[i - 1] 1赋值。这个写法在“评分持续上升”的用例上会得到正确结果但一旦中间出现评分下降或相等就会漏掉“至少 1 颗”的约束。举个例子ratings [2, 1]第一轮如果从索引 1 开始ratings[1] ratings[0]不执行赋值candies[1]就一直是 0最后总数就是 1显然是错的。正确做法是初始化candies [1] * n把“至少 1 颗”直接做进去。你也可以在循环里对下降情况显式赋值为 1但那样代码更啰嗦没必要。4.3 雷区三评分相等时误用了“必须相等”的规则题目只要求“评分高的人拿更多”并没有要求“评分相等的人拿一样多”。但很多人会不自觉默认相等评分应该分配相同糖果然后在代码里写成if ratings[i] ratings[i-1]: candies[i] candies[i-1]这会对总数造成不必要的影响。正确做法是评分相等时不要做任何额外处理保持当前值为 1或者第一轮里已经由更早的上升段确定的值。举个例子ratings [1, 2, 2, 3]正确分配是[1, 2, 1, 2]总数 6。如果你把两个 2 分给相同数量可能得到[1, 2, 2, 3]总数 8那就不是最少糖果数了。4.4 雷区四以为一次遍历就能搞定这个想法很有诱惑力因为很多贪心题都是一次遍历解决的。但糖果问题有左右两个方向的约束一次遍历要么只能处理一个方向要么需要在同一个位置反复回退。比如你尝试从左到右同时比较左右邻居遇到“右边更低”时回到上一个位置去修改这种回溯在极端情况下复杂度会退化到 O(n^2)而且很容易写错。记住一个判断标准当一个问题同时存在“从左看”和“从右看”两种约束时先想想能不能拆成两个独立的遍历。糖果、接雨水、乘积除自身之外很多数组题都有这种“两遍扫描”套路。4.5 一个可以直接抄的测试用例清单我在本地练这道题的时候会固定跑下面这组用例能把大部分边界问题暴露出来输入 ratings期望最少糖果说明[1, 2, 3]6纯上升分配应为[1, 2, 3][3, 2, 1]6纯下降分配应为[3, 2, 1][1, 3, 2]4山峰型分配应为[1, 2, 1][1, 3, 2, 1]7山峰斜坡分配应为[1, 3, 2, 1][1, 2, 2, 3]6存在相等评分[1]1单元素边界[]0空数组边界跑这些用例时尤其注意第三行[1, 3, 2]和第四行[1, 3, 2, 1]的差异。前者两类遍历后结果都是 4后者如果你只做一次从左到右会得到错误的 5。5. 把贪心串成体系糖果、分发饼干与跳跃游戏25.1 和分发饼干一起看贪心的“局部决策”长什么样分发饼干是一道经典的贪心入门题每个孩子有一个胃口值每块饼干有一个尺寸值饼干尺寸大于等于孩子胃口才能满足孩子问最多能满足几个孩子。解法是先排序然后从胃口最小的孩子开始找最小能喂饱他的饼干。这道题和糖果问题的共性在于每个决策都只需要考虑“当前最小/最紧迫”的需求就能保证整体最优。区别在于分发饼干的约束是“一人最多一块饼干没有相邻关系”所以排序双指针就够了糖果问题的约束是“相邻关系”所以需要两次遍历来满足两个方向的比较。5.2 和跳跃游戏2一起看贪心维护的“最远覆盖”跳跃游戏2的问题是给定一个数组每个元素代表你在该位置最多能往前跳多远求从起点跳到最后一个位置的最少跳跃次数。这道题的贪心策略是在当前能跳到的范围内选一个能让下一步覆盖范围最大的位置作为跳点而不是每次都跳最远。最近“跳跃游戏2 贪心算法”这个词频繁出现在各种题单热榜上它和糖果问题放在一起看特别有意思跳跃游戏2是“最大化覆盖范围”的贪心糖果问题是“最小化必要分配”的贪心。一个向右扩展一个逐点约束但它们共享同一个底层逻辑每一步都只根据当前范围内的信息做决策而且决策一旦做出就不会对后续产生“后效性”。什么叫“后效性”就是这一步的选择会影响下一步可选范围或者下一步需要回退修改。分发饼干、跳跃游戏2、糖果问题之所以能用贪心都是因为它们没有这种后效性。反过来如果一个问题存在后效性比如背包问题那贪心就不适用需要动态规划。5.3 怎么判断一道题能不能用贪心三个快速检查点我在刷了上百道贪心题之后总结出三个检查点适合拿到新题时快速判断第一个检查点局部最优是否可合成全局最优。你可以假设“这一步取最优解”然后检查剩余子问题的解空间是否依然完整。如果剩余部分不受影响贪心通常可行。第二个检查点是否存在单调传递性。糖果问题里“评分更高 → 糖果更多”是沿相邻关系单调传递的所以可以按方向扫描。分发饼干里“排序后从小到大匹配”也是单调传递的。第三个检查点约束能不能拆成几个独立方向。糖果问题能拆成“从左看”和“从右看”两个方向分别解决再合并。如果约束错综复杂、无法拆分贪心大概率行不通。我个人的体会是糖果题是最适合用来理解“约束拆解 方向扫描 最大值合并”这三板斧的题目之一。它没有复杂的数学证明代码量又短非常适合在面试前临时过一遍手感。最后再分享一个小技巧做这类数组题目时不要急着写代码先在纸上画出每个位置的“左约束”和“右约束”再想清楚取交集还是取并集。糖果问题就是典型的“两个方向的约束取并集”而取并集在代码里常常表现为取最大值。把这个直觉刻进脑子里下次遇到“同时满足两组条件”的数组题你至少能少走一半弯路。