LeetCode 第135题题名就叫Candy中文社区一般翻译成分发糖果或者干脆叫糖果题。我在准备算法面试时第一次划到它以为就是个简单的数组遍历结果自己闷头写了快四十分钟提交还挂掉两个case。后来把贪心那道坎迈过去才发现这个题出得相当讲究。先交代一下题面一排孩子每人身上有一个评分现在给孩子们发糖果规则只有两条——每个孩子至少拿1颗相邻两个孩子里评分更高的一方必须拿得比另一方多。问的是最少需要准备多少颗糖果。这个最少一出来基本就是在暗示贪心。我在各种题单上反复看到同一句话糖果 贪心或者糖果 贪心算法说的都是这道题。今天聊完它之后我会把同样高频的跳跃游戏2 贪心算法拉出来做横向对比因为这两个题一个处理相邻约束一个处理区间覆盖刚好是贪心算法最典型的两种形态放在一起理解会特别通透。1. 糖果题的本质两个同时生效的约束让一次扫描直接失效1.1 逐字拆题把两条规则翻译成算法约束在动手写代码之前一定要把题面里的字抠清楚。这里最容易漏掉的不是至少1颗而是相邻两个孩子里这个限定。它意味着每个孩子同时承担两段关系和左边比一次和右边比一次。如果评分比左边高糖果数要比左边多如果评分比右边高糖果数也要比右边多如果两边都比自己低那它需要同时满足两个多于约束最终要取两个约束里更严格的那个。如果两边都比自己高它反而只需要拿最低的1颗就行。这个地方是很多解法第一次翻车的原因。你只盯着数组从左往右推一遍等于只承认了右边比左边高时右边要多拿这一半规则另一半完全没处理。我最初就是这么干的把数组从左扫到右遇到上升就给前一个孩子加一颗看起来顺理成章结果一提交遇到递减序列直接全挂。因为递减序列里评分更高的孩子全在左边从左往右扫的时候它们早早就被定了1颗后面根本没有回头修正的机会。1.2 一次扫描为什么救不回来递减序列和峰值的连锁反应用一个极端例子说明。假设评分是 [5,4,3,2,1]从左往右做一次贪心所有相邻关系都是左边比右边高从左往右看时每个孩子的评分都不比前一个高所以什么都不用改最后5个孩子各拿1颗。这显然不对。因为第一个孩子评分5比第二个孩子4高至少要拿2颗第二个孩子评分4又比第三个孩子3高而且第一个孩子还压着它所以第二个孩子也必须比第三个拿得多这样连锁下来最省糖的方案就是 [5,4,3,2,1]总和15。那能不能在从左往右扫的过程中遇到右侧评分更低时回过去给左边的一串孩子补糖理论上可以但从代码实现看你每遇到一次下降都可能要往回更新一段孩子最坏情况下会变成O(n^2)的操作完全违背了贪心题一遍扫完的初衷。所以标准解法干脆把两个方向拆开先从左往右处理一遍再从右往左处理一遍各管一半约束时间复杂度稳定在O(n)。1.3 常见错误打开方式排序分糖、均值分糖为什么必错见过评论区有人说把评分排个序按排名从低到高发糖不就行了。这个想法初看挺合理但它完全忽略了相邻这个位置约束。排序只反映全局的相对高低不反映谁和谁挨着。你把评分最高的孩子先拿一堆糖果可它旁边的孩子可能评分只差1也可能评分差出一大截它们之间要求的糖果差完全不一样。更麻烦的是一个高分孩子可能被两个低分孩子夹在中间它只需要比自己两侧低分孩子多1颗排序法会强行给它一大把纯属浪费。另一种常见做法是先所有人拿一样的再根据相邻关系微调。这个思路离正确解法很近了本质上就是想做两遍扫描但很多实现里少了取max那一步导致在波峰处漏算或者反过来把前一遍的关系破坏掉。这两类错误都说明一个道理糖果题不只是在找谁分高而是在找一个同时满足双向相邻约束的最小分配方案任何只看单方向或全局排序的思路都会在不该错的地方出错。2. 双向贪心的拆解左规则、右规则与合并时的max逻辑2.1 左规则第一遍扫描到底在做什么正确解法一般分两段。先说第一段我习惯管它叫左规则。先初始化一个长度为n、值全是1的数组candies表示每个孩子先拿保底的1颗。然后从 i 1 遍历到 n-1如果 ratings[i] ratings[i-1]就把 candies[i] 更新为 candies[i-1] 1否则不动。这一步保证的是对于每一对相邻的 (i-1, i)只要右边的评分比左边高右边的糖就一定比左边多。注意它不会去管左边比右边高的反向关系哪怕左边孩子因此吃亏也先等第二遍处理。用生活化的方式理解就是你先给所有孩子一人发一颗保底糖然后从左往右走看到谁比左边的孩子评分高就给谁的发糖盒里再加一颗。走完这一遍整个队伍里右侧更高的相邻关系全部满足但左侧更高的关系还完全没动。2.2 右规则为什么必须从右往左倒着扫第二遍从 i n-2 遍历到 0如果 ratings[i] ratings[i1]就执行 candies[i] max(candies[i], candies[i1] 1)。这里有三个细节必须讲清楚为什么倒序遍历为什么取max而不是直接赋值以及这样真的还能保证最少吗。先说方向。第二遍要修正的关系是左边评分比右边高时左边要多拿它依赖的是右侧邻居的结果。如果依旧从左往右扫你处理 i 的时候右侧邻居 i1 的糖果数可能还没被本轮更新过可能还是上一轮的值甚至是初始值1拿它做基准算出来的左边糖数会偏小后面又要回头再改。倒序遍历可以保证处理 i 时i1 已经在这一轮里被更新过右侧基准是可信的。再说取max。第一遍已经把右边比左边高的约束写进了candies数组这个约束不能被第二遍覆盖掉。如果第二遍直接写成 candies[i] candies[i1] 1很可能把第一遍里更大的值覆盖成更小的值导致某些场景下右边孩子评分明明高糖果数却反而比左边少。用 max 就相当于只在新的右规则给出更大需求时才提升否则保持原值。两个方向的约束在同一个数组上叠加互相不破坏才能保证最终方案合法。2.3 纸上演算一次完整流程光说逻辑不如手跑一遍。我用一个有升有降的数组做例子ratings [1,3,4,3,2]。初始化 candies [1,1,1,1,1]。第一遍左规则i1ratings[1]3 1candies[1] 11 2得到 [1,2,1,1,1]i2ratings[2]4 3candies[2] 21 3得到 [1,2,3,1,1]i3ratings[3]3 4不动i4ratings[4]2 3不动第二遍右规则i3ratings[3]3 2candies[3] max(1, 11) 2得到 [1,2,3,2,1]i2ratings[2]4 3candies[2] max(3, 21) 3不动i1ratings[1]3 4不动i0ratings[0]1 3不动最终结果是 [1,2,3,2,1]总和9。这个例子覆盖了波峰评分4的孩子和右侧下降段可以看到最终糖果数呈现一个以波峰为顶、向两侧递减的形状既满足左边关系也满足右边关系而且每个位置都是满足约束的前提下能拿到的最小值。阶段candies 状态初始[1,1,1,1,1]左规则结束后[1,2,3,1,1]右规则 i3[1,2,3,2,1]右规则 i2[1,2,3,2,1]最终[1,2,3,2,1]2.4 复杂度分析与空间优化空间时间复杂度是O(n)两个循环各扫一遍每个位置常数操作。空间复杂度是O(n)因为要存candies数组。如果面试官追问能不能优化空间答案是能存在O(1)空间的贪心实现核心思路是用一个上一个孩子分到的糖数加当前递减段长度来同步维护不需要存完整数组。但那个写法非常绕处理相等评分和递减段边界时很容易把自己绕进去我在实际面试里不太建议优先写后面第3节会专门说这个事。先保证一个清晰、正确、可解释的两遍扫描版本比追求空间更省一步到位更重要。3. 代码实现与边界case从能跑到跑稳3.1 最小可用实现把这套逻辑写成代码非常短。我日常刷题用Python比较多下面是完整实现def candy(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 # 右规则倒序保证左侧评分高的相邻关系同时不破坏左规则 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)换成Java或者C也大同小异无非是把数组初始化为全1、注意i的取值边界。核心逻辑就两句话两个方向的贪心扫描合并时取max。很多题解里会把第一个循环叫从左往右扫第二个叫从右往左扫你只要记住每次扫描只负责一个方向的相邻约束就够了。3.2 边界case怎么测写完之后建议第一时间拿几个边界输入验证而不是直接提交尤其是这种看起来代码量很少的题隐患常常藏在对题意的理解决定下。下面几个case我每次跑都会过一次评分输入期望输出简要说明[1]1只有一个孩子保底1颗即可[1,1,1]3评分全相等相邻不需要更多每人1颗[1,2,3]6严格递增糖果依次为1,2,3[3,2,1]6严格递减糖果依次为3,2,1[1,3,4,3,2]9有波峰有下降是前文演算过的综合场景这几个case分别覆盖了单元素、相等评分、单向递增、单向递减和混合波峰。如果你写的代码能全部通过大概率逻辑是没问题的。3.3 现场手写时最容易漏的三件事第一忘记初始化全是1。有的同学直接在默认0的数组上判断最后结果会整体偏小而且很难一眼看出问题。第二右规则忘记写max。这个错法很隐蔽因为很多测试样例里max之后值根本没变结果一跑大用例就露馅所以一定要在代码里显式写max。第三倒序遍历的边界写错。比如从 n-1 开始或者第二个参数写成0写成0会把下标0漏掉这两种都会让结果不对。建议动手写的时候直接在纸上把 i 的范围写出来左规则从1到n-1右规则从n-2到0两头都要闭合。4. 从糖果到跳跃游戏2贪心在不同题型中的两种面孔4.1 跳跃游戏2的贪心解法和直觉说完糖果再来看看热词里那个跳跃游戏2 贪心算法。LeetCode 45题题目是给一个非负整数数组nums你最初在下标0每个数字代表你在当前位置最多能往后跳多远问到达最后一个下标需要的最少跳跃次数。很多人第一次拿到这题会想用动态规划dp[i]表示跳到位置i的最少步数然后枚举能跳到i的前驱位置复杂度是O(n^2)。但贪心可以把它压成O(n)。核心思路是维护两个变量当前这一步能够覆盖到的右边界 cur_end以及在这个覆盖范围内所有位置能跳到的最远位置 farthest。遍历每个位置时先更新 farthest max(farthest, i nums[i])当 i 走到 cur_end 时说明必须迈出下一步了步数加一同时把 cur_end 更新成 farthest。代码长这样def jump(nums): n len(nums) if n 1: return 0 steps 0 cur_end 0 farthest 0 for i in range(n - 1): farthest max(farthest, i nums[i]) if i cur_end: steps 1 cur_end farthest if cur_end n - 1: break return steps用 nums [2,3,1,1,4] 走一遍初始 cur_end0i0时 farthest2i等于cur_end于是steps1cur_end2i1时 farthestmax(2,4)4i2时 i等于cur_endsteps2cur_end4此时已经覆盖到终点结束。返回2正好是最少跳跃次数。这个贪心最精妙的地方在于它并没有在每一步真正选择从哪个位置跳而是把每一步能到达的所有位置看成一个区间在这个区间里不断刷新最远可达点直到必须跨出下一步时才把步数加一。这个设计让全局的最少步数问题被拆成了若干段区间能否覆盖到更远的局部问题每一段都只关心最远能到哪不需要回头。4.2 糖果与跳跃游戏2的异同把两题放在一起看会很有意思。糖果题关注的是相邻两个孩子之间的评分差跳跃游戏2关注的是当前位置能覆盖到多远糖果题需要正反两遍扫描才能把双向约束合并跳跃游戏2只需要一遍单向扫描就能推进区间边界。但它们底层的贪心逻辑是一致的每一步只做当前约束下的最优决策并且这个决策不会因为后续步骤而需要整体回退顶多是在局部做修正或者把边界往前推。对比维度糖果题跳跃游戏2题干核心相邻评分高者拿更多糖从起点到终点的最少跳跃次数贪心点分别满足左/右邻居关系后合并每一跳都选当前区间内最远可达点遍历方向从左到右一遍从右到左一遍一次从左到右关键维护状态每个孩子当前糖果数当前覆盖边界和下一步最远边界复杂度O(n)时间O(n)空间O(n)时间O(1)空间这个表格也是我在复习时经常看的它帮我建立了一个印象贪心题只是看起来形态各异内在的局部最优 无需回溯骨架是一致的。4.3 从两道题总结贪心题长相刷了大概几十道贪心题之后我会下意识先问自己三个问题。第一题面里有没有最少最多这类最值词有的话贪心属于高优先级的候选。第二约束是不是只存在于局部相邻关系或者连续区间里如果是大问题通常可以切成一维方向上的局部问题。第三如果尝试动态规划状态转移是不是只依赖前一步或者某个前缀信息如果是贪心往往比DP写得短得多。糖果题正好是第一个和第二个特征的组合跳跃游戏2则是第二个和第三个特征的组合。当然满足这些特征不代表一定能贪心还需要在纸上尝试构造反例。比如糖果题反例就得找那种只满足一个方向但破坏另一个方向的评分序列一旦发现两遍扫描能兜住你才敢放心写。5. 刷题过程中的常见误区和实操心得5.1 贪心还是DP这题为什么不用DP新手看到糖果题每个孩子的状态依赖左边和右边很容易想到动态规划。实际上用DP也能做糖果题但状态设计要同时考虑左右两个方向的影响转移方程绕来绕去写起来很痛苦。贪心之所以优雅是因为每条约束都只是相邻两个孩子之间的比较一个孩子的糖果数只会因相邻孩子的糖果数而变大不存在跨层、跨位置的影响所以两遍扫描就能收敛到全部满足。跳跃游戏2也一样用DP做当然能过小数据但状态转移需要枚举所有能到达当前点的前驱位置复杂度O(n^2)。贪心用维护区间边界的方式把每个位置只扫一遍就拿到了全局最少步数。所以我的判断标准是当局部决策足够局部时优先尝试贪心一旦发现当前决策会影响到很远位置的全局结果或者需要大量状态重叠计算时才老老实实回头写DP。5.2 为什么要求最少糖果时取max仍然不矛盾初学者最容易困惑的一点是题目不是要求最少吗为什么第二遍还要取max把糖果数变大这个矛盾其实是个误解。这里的最少指的是在所有满足约束的方案里取总数最小不是构造过程中每个位置尽量小。第一遍给出的每个数已经是只满足左规则时的最小值第二遍为了满足右规则某些位置不得不提高取max正是只提高必要的位置并且提高到恰好满足右规则的最小值所以结果依然是全局最优。举个例子评分 [1,3,4,3,2] 里评分4的孩子第一遍已经拿到3颗第二遍即使它右侧是下降段也不需要再加因为3已经大于右侧孩子所需的2颗了。而评分3的那个孩子第一遍只拿到1颗第二遍发现它右侧评分2比它低于是必须提到2颗。这种不得不提高的精确判断才是整个算法的核心。5.3 现场面试时的表述顺序分享一个我的实际经验。面试碰到这种题不要急着贴代码先把思路按三步说出来第一指出题目有两个方向的相邻约束不能一次扫描解决第二先从左到右扫一遍保证右侧更高的关系全部满足第三再从右到左扫一遍在不破坏前一遍结果的前提下用max修正左侧更高的关系。最后再说复杂度的O(n)时间和O(n)空间。这套表述方式能让面试官快速确认你理解了为什么需要两遍和为什么用max比闷头写代码安全得多。如果你上来就写O(1)空间版本虽然看起来很厉害但那个版本对递减段长度和相等评分的处理极其容易出错一旦卡壳反而暴露准备不足。笔试也一样优先写两遍扫描版本把正确性拿稳优化留到有时间再谈。最后说一下我自己刷这类题的习惯。遇到题目里有相邻区间最少最多这些词我会先把局部决策是什么想清楚再想这个局部决策能不能合成全局最优。糖果题的局部决策是相邻孩子的大小比较跳跃游戏2的局部决策是当前区间能伸多远。前者用两遍扫描后者用边界推进看着完全不同落到代码里其实都是几个临时变量加一层循环。把这个感觉抓住比死记某道题的做法有用得多。