1. 题目解读拆完条件你会发现它其实是个“双向约束”“糖果【贪心】”这道题在算法面试题单里出现的频率相当高。题面的故事很简单一排孩子每人一个评分现在要给大家发糖果规则有三条——每个孩子至少分到一颗相邻两个孩子里评分更高的那个必须拿到更多糖果最后要让糖果总数最少。我第一次看到这道题时第一反应是“这不就是逐个比较大小吗”但真动起手来才发现它远没有想象的那么简单。这道题之所以被贴上“贪心”的标签是因为它最漂亮的解法确实是一个标准的贪心策略不去做全局规划而是把问题拆成两个单向的约束分别用贪心跑一遍再把结果合并。理解了这个套路你不仅会做这一道题还能顺带把“跳跃游戏2 贪心算法”这类问题看穿一大半。这篇文章我把自己从第一次写错到彻底吃透的过程完整讲一遍代码、推导、踩坑都放在里面适合准备面试的读者也适合刚接触贪心算法想建立体系的新手。1.1 先把原题的三个约束压到最简很多资料喜欢直接甩题解但我觉得先做数学化翻译更重要。题目给的是一个评分数组 ratings长度记为 n我们要构造一个糖果数组 candies满足三条硬性条件candies[i] ≥ 1即每个孩子至少有一颗糖。如果 ratings[i] ratings[i - 1]那么 candies[i] candies[i - 1]。如果 ratings[i] ratings[i 1]那么 candies[i] candies[i 1]。在满足上述条件的所有构造里sum(candies) 最小。注意条件里写的是“严格大于”不是“大于等于”。这个细节非常要命很多错误提交都是从这里来的。当两个孩子评分相等时题目完全不要求谁的糖更多两边可以拿一样多当然也允许一边多一边少只要不加糖也能满足相邻约束就行。把问题翻译成数组约束后核心难点就暴露出来了每个位置 i 的糖果数同时受左边邻居和右边邻居两个方向的影响。评分高的孩子要同时压过左右两边糖果数必须取两边约束的较大值。这就是典型的“双向约束”问题也是为什么一眼看过去总觉得应该有个简单规则但怎么写都容易漏掉另一边。1.2 为什么一次贪心走不通我最初的想法很朴素从左往右扫一遍只要发现右边孩子评分更高就把右边孩子的糖果数设成左边加一。这个思路只对了一半。比如 ratings [1, 3, 2, 1]从左到右扫完得到的是 [1, 2, 1, 1]总和 5。但这个答案合法吗检查一下就会发现第三位孩子评分 2 比第四位孩子评分 1 高可糖果数都是 1并不满足“评分高者必须拿更多”的约束所以这个结果直接被判非法。那从右往左扫一遍呢处理 [1, 3, 2, 1] 会得到 [1, 3, 2, 1]看起来对了但其实只是这个例子碰巧对了。换个场景比如 ratings [1, 2, 3, 4]从右往左扫会得到 [1, 1, 1, 1]显然第二位孩子评分 2 比第一位评分 1 高糖果却一样又是非法解。核心原因在于一次贪心遍历只能携带一个方向的信息。从左到右你在更新第 i 个孩子时只知道左边邻居的情况还不知道右边邻居会不会对它的糖果数提出更高要求从右到左也是同理。每个孩子的最终值由左右两个邻居共同决定只扫一遍必然丢掉一半约束。这是这类“相邻比较”问题最常见的思维陷阱。1.3 双向约束的正确打开方式左右各贪心一趟既然一个方向的贪心带不全所有信息那很自然的想法就是分两次跑分别把两个方向的下界算出来最后再合并。这个思想在算法题里非常常见叫作“拆约束”。具体来说第一趟从左到右遍历只维护“右边评分高时右边糖要多”的规则得到数组 left。第二趟从右到左遍历只维护“左边评分高时左边糖要多”的规则得到数组 right。最终 candies[i] max(left[i], right[i])。为什么取 max 就是最优解因为对于任意一个孩子 ileft[i] 是它只考虑左约束时必须达到的最小值right[i] 是它只考虑右约束时必须达到的最小值。任何合法方案里candies[i] 必须同时不小于这两个值而把所有位置都取 max 得到的数组能同时满足两个方向的约束所以它就是合法方案里最小的那一个。这个证明思路建议面试时主动讲出来比直接背代码有说服力得多。2. 标准解法两次贪心遍历的思路与完整实现2.1 从左到右让每个孩子先满足“右边更严格”的约束先初始化 left 数组所有元素都是 1。为什么初始值是 1 而不是 0因为题目规定了每个孩子至少分到一颗这个下界必须先满足后续更新也只能在 1 的基础上做加法。然后从左往右遍历从第 1 个位置开始第 0 个位置左边没人不用比较。如果 ratings[i] ratings[i - 1]说明当前孩子比左边邻居评分高需要比左边孩子的糖果数多一颗否则ratings[i] ≤ ratings[i - 1]当前孩子对左边没有“必须更多”的要求保持初始的 1 就行。这趟遍历结束后left 数组的含义就是“假设只考虑左边邻居约束每个孩子至少要拿多少糖”。注意这个数组还不满足右方向约束千万不要急着输出。2.2 从右到左把左边约束补上并逐位取最大值第二趟遍历从最后一个位置开始往左移动。如果 ratings[i] ratings[i 1]说明当前孩子比右边邻居评分高那么它的糖果数必须比右边的多这时右边孩子的“右方向需求”会传导过来当前孩子的右方向下界就是 right[i 1] 1否则当前孩子对右边没有更多要求可以保持 1。这里有个特别容易搞错的点第二趟结束时不能直接覆盖 left[i] 把 right[i] 写进去。因为 left[i] 保存的是左方向约束的必须值right[i] 是右方向约束的必须值两个都必须满足缺一不可。正确做法是对两个数组逐位取 max把要求合并起来。我见过很多初学者在这一步直接把 left 覆盖掉导致左侧约束丢失提交自然过不了。2.3 完整代码C / Python先给最直观的数组版本这个版本空间复杂度 O(n)时间复杂度 O(n)适合面试时先讲清楚思路int candy(vectorint ratings) { int n ratings.size(); vectorint left(n, 1), right(n, 1); // 从左到右满足右边评分更高的约束 for (int i 1; i n; i) { if (ratings[i] ratings[i - 1]) { left[i] left[i - 1] 1; } } // 从右到左满足左边评分更高的约束 for (int i n - 2; i 0; --i) { if (ratings[i] ratings[i 1]) { right[i] right[i 1] 1; } } int ans 0; for (int i 0; i n; i) { ans max(left[i], right[i]); } return ans; }Python 版本逻辑完全一致写法上更简洁def candy(ratings): n len(ratings) left [1] * n right [1] * n for i in range(1, n): if ratings[i] ratings[i - 1]: left[i] left[i - 1] 1 for i in range(n - 2, -1, -1): if ratings[i] ratings[i 1]: right[i] right[i 1] 1 return sum(max(left[i], right[i]) for i in range(n))代码很短但每一行都有含义。left、right 初始化为 1 是第一约束的直接体现两个循环的顺序不能换因为 left 依赖从左到右的递推right 依赖从右到左的递推最后 sum 里用的是 max不能是 left right也不能是单独某一个数组。2.4 样例推演把每一步数组变化都走一遍只看代码不跑一遍很容易觉得自己懂了但实际动手就忘。我选两个例子手动把数组每一步的演变写出来。第一个例子ratings [1, 0, 2]这是官方示例用来理解基础流程。从左到右位置 iratings[i]left[i]触发条件011初始化左边无人1010 1不更新2222 0left[1] 1 2left [1, 1, 2]。从右到左位置 iratings[i]right[i]触发条件221初始化右边无人1010 2不更新0121 0right[1] 1 2right [2, 1, 1]。逐位取 max得到 candies [2, 1, 2]总和 5。检查一下第一位评分 1 比第二位 0 高所以 2 1 满足第三位评分 2 比第二位 0 高所以 2 1 满足每个位置都至少 1。这是最优解因为两个“波峰”位置的最小需求都是 2。第二个例子我选一个稍复杂的来展示为什么必须取 maxratings [1, 3, 2, 1]。从左到右left [1, 2, 1, 1]。这里只在 i1 时触发了一次更新因为 3 1。从右到左i3right[3] 1。i2ratings[2]2 ratings[3]1所以 right[2] right[3] 1 2。i1ratings[1]3 ratings[2]2所以 right[1] right[2] 1 3。i0ratings[0]1 ratings[1]3保持 1。right [1, 3, 2, 1]。逐位取 maxcandies [1, 3, 2, 1]总和 7。这个例子非常典型如果不取 max 只保留 right第一个位置没问题如果不取 max 只保留 left第三个位置评分 2 会拿到 1和右边评分 1 的孩子一样直接违反规则。只有取 max 才能把右边的下降约束完整保留下来。3. 再进一步空间复杂度降到 O(1) 的结算式写法3.1 核心洞察糖果数量可以按“波形”结算两次遍历的数组版本已经能通过所有测试但很多追求极致的读者会问能不能把空间压到 O(1)能但思路需要换一个角度。观察 left 和 right 数组你会发现里面存的本质上不是随机值而是连续递增或递减的“长度”。从左到右的更新其实是在数递增坡有多长从右到左的更新是在数递减坡有多长。糖果总数最终等于每个波峰的左侧坡长和右侧坡长取 max 之后累加。于是我们可以不存数组只维护几个关键变量边遍历边结算。具体来说需要维护三个状态pre当前孩子如果处于上升段它相对左边孩子的增量。遇到评分相等时它要重置为 1。dec当前已经连续下降了多少步。inc最近一次结算出来的峰值。它代表当前这段波形里波峰至少需要多大。在从左到右的遍历过程中遇到上升趋势时pre 递增答案累加 pre遇到下降趋势时dec 递增答案累加 dec遇到评分相等时说明波形断了两边都不需要比较pre 和 dec 全部重置。这个思路成立的前提是每个新加入的孩子对答案的增量只取决于它自己和前面一个孩子的比较结果。这一点和两次遍历的核心逻辑完全一致只是把“存下每个位置的值”换成了“在移动过程中累加增量”。3.2 O(1) 代码实现int candy(vectorint ratings) { int n ratings.size(); if (n 0) return 0; int total 1; // 第一个孩子先给 1 颗 int inc 1; // 当前峰值的最大高度 int dec 0; // 当前下降段长度 int pre 1; // 上一个孩子分到的糖 for (int i 1; i n; i) { if (ratings[i] ratings[i - 1]) { dec 0; if (ratings[i] ratings[i - 1]) { pre 1; } else { pre pre 1; } total pre; inc pre; } else { dec; if (dec inc) { dec; } total dec; pre 1; } } return total; }这段代码里有几个看起来很“神来之笔”的分支我逐个解释。第一个是if (dec inc) dec。这个判断解决的是“下降段长到足以推翻之前的峰值”的情况。比如 ratings [1, 3, 2, 1]从左到右走到第三位时inc 是 2代表波峰评分 3 的孩子按左约束只需要 2当下降到第四位时dec 累加到 2此时右侧约束要求波峰至少是 3因为波峰后面要依次排 2、1。如果不把 dec 自增total 就会少算 1输出 6 而不是正确的 7。第二个是pre 1。每当遇到下降说明当前这个孩子是下降段的起点它自己作为“新的谷值起点”下一步如果又开始上升它的 pre 必须从 1 重新开始算。这个重置非常容易忘忘了就会出现累加错误。3.3 用三个斜坡样例验证并解释特判我实际验证时跑了三种典型波形第一种严格递增 ratings [1, 2, 3, 4]。total 的累加过程是 1 2 3 4 10左边坡长直接决定结果下降段 dec 一直是 0inc 一直等于 pre。这个 case 很直观糖果就是 1、2、3、4。第二种严格递减 ratings [4, 3, 2, 1]。total 的累加过程一开始 total1i1 时 dec1total 1 → 2i2 时 dec2total 2 → 4i3 时 dec3total 3 → 7。等等严格递减只需要 4 3 2 1 10这里怎么少算了这里要特别提醒我上面这个“验证”是错的因为严格递减时实际分配应该是 [4, 3, 2, 1]而不是逐步累加 1、2、3。问题出在 dec 递增时并没有把之前所有下降层级的增量都补上。仔细想想每次进入新的下降步不只是给当前孩子加 dec 颗还要给整个下降段里的每个孩子各加 1 颗所以 total 的增量应该是 dec 的和即 1 2 3 4 10。上面代码里total dec累加的是 1、2、3、4 吗再看一遍代码逻辑i1 时 total 1total2i2 时 total 2total4i3 时 total 3total7。这显然不是 10。我的 O(1) 实现写错了要修正才能发布。标准做法是每次下降时total dec 1同时当 dec 达到 inc 时还要再补 1 给峰值。让我重新给一版经过多次验证的 O(1) 代码int candy(vectorint ratings) { int n ratings.size(); if (n 0) return 0; int total 1; // 第 0 个孩子 int pre 1; // 上一个孩子分到的糖 int dec 0; // 当前下降段长度 int inc 1; // 最近一次上升段结算出的峰值 for (int i 1; i n; i) { if (ratings[i] ratings[i - 1]) { dec 0; if (ratings[i] ratings[i - 1]) { pre 1; } else { pre; } inc pre; total pre; } else { dec; if (dec inc) { total dec; } else { total dec 1; } pre 1; } } return total; }用这版重新验证严格递减 [4, 3, 2, 1]total1i1 dec11 inc1 不成立total 2 → 3i2 dec22 1 不成立total 3 → 6i3 dec33 1 不成立total 4 → 10。正确。再验证 [1, 3, 2, 1]total1i1 上升pre2inc2total3i2 下降dec11 2 成立total4i3 下降dec22 2 不成立total437。正确。为什么dec inc用小于而不是小于等于因为当 dec 等于 inc 时新加入的下降孩子会把波形变成“波峰需要再抬高 1”的情况左侧坡长 inc 说明峰值至少要 inc右侧下降段长度 dec 说明峰值至少要 dec 1两者相等时峰值被迫抬高所以要多加 1。这个边界是整个 O(1) 解法里最容易错的地方我面试时被问过两次都没有当场写过这个版本因为它确实太容易写错了。所以我的建议是日常刷题和面试优先写两次遍历的数组版本空间 O(n) 完全可接受逻辑也清晰O(1) 版本更适合作为扩展理解展示你对贪心的理解深度但别在高压环境下硬写容易翻车。4. 从糖果到跳跃游戏2同一套贪心思维怎么迁移4.1 先看跳跃游戏2 的贪心解跳跃游戏2 的题面是给定一个非负整数数组 nums初始位置在索引 0nums[i] 表示你在位置 i 最多能往后跳多远保证总能到达最后一个位置求最少跳几次。这道题和“糖果”表面上八竿子打不着但核心都是贪心。贪心策略非常简洁在“当前这一跳能覆盖到的区间”里找到能跳到的最远位置一旦走到区间边界就强制起跳一次。这里的关键变量有两个end当前这一跳能够覆盖的右边界。farthest当前区间内所有位置能跳到的最远距离。每次遍历到 end 时跳跃次数加一end 更新成 farthest。这样每跳都把下一步的覆盖范围最大化局部最优的叠加就是全局最优。int jump(vectorint nums) { int n nums.size(); int end 0; int farthest 0; int jumps 0; for (int i 0; i n - 1; i) { farthest max(farthest, i nums[i]); if (i end) { jumps; end farthest; } } return jumps; }用 nums [2, 3, 1, 1, 4] 推演一遍一开始 end 0farthest 0jumps 0。i0 时farthest 变成 2i 等于 end所以 jumps1end2。i1 时farthest 变成 max(2, 13)4但 i 不等于 end1 ! 2。i2 时farthest 已经到 4i 等于 end所以 jumps2end4。循环结束输出 2答案正确。这里有个很多初学者会踩的坑循环只走到 n-2不处理最后一个位置。因为最后一个位置不需要再跳如果你的循环条件是 i n结果会多算一跳。4.2 两题的“局部状态”对比糖果和跳跃游戏2 用到贪心时底层状态变化其实很像我整理了一个对比表对比维度糖果问题跳跃游戏2约束来源左右相邻两个孩子当前位置能覆盖的跳跃区间贪心动作先分别满足单方向约束再取 max在区间内选择能到达的最远点需要的状态left、right 两个数组或 inc/dec 变量end、farthest 两个变量决策无后效性更新只依赖相邻前一个值每次起跳后旧区间无需再次考虑复杂度O(n) 时间O(1)/O(n) 空间O(n) 时间O(1) 空间糖果的核心是“把双向约束拆成两个单向约束分别贪心”跳跃游戏2 的核心是“把区间看成整体每跳一步就让区间覆盖范围最大化”。两者都不需要回溯修改之前的答案这是贪心能用的根本原因。4.3 用“决策无后效性”判断能不能用贪心想真正掌握贪心不能靠背题得理解“什么时候贪心成立”。我习惯用一个词来判断无后效性。通俗地说就是“当前决策做完之后不会影响后续状态的计算基础”。糖果题里从左到右更新 left[i] 时只依赖 left[i - 1]右边还没看这个决策不会因为后面某个高分孩子的出现而被推翻。那为什么还需要从右到左再跑一遍因为 left 数组只是局部下界右方向约束要靠另一趟补齐补齐操作是在另一个维度上互相独立的。跳跃游戏2 里每一跳选最远点选完之后下一跳的起点区间完全由新 end 决定旧区间内部怎么跳的细节根本不再需要。如果一个问题里局部最优决策导致后面的最优解必须用另一个局部次优来补偿那贪心就失效了。比如零钱兑换面额是 1、5、11目标 15贪心先拿 11剩下 4 需要 4 个 1总共 5 枚但最优解是 5553 枚。这里局部拿最大面额反而害了全局就是因为“先拿大面额”这个决策有后效性它锁死了后续凑数的结构。所以看到贪心题第一件事不是写代码而是先问这个决策会不会让后面的步骤吃亏5. 高频易错点与调试经验这些坑我全踩过5.1 糖果题的五个常见提交错误第一个是初始化成 0。如果把 left、right 初始化为 0最终结果会出现 0 颗糖的非法解。记住每个孩子的下限是 1不是 0这是题目的明确要求。第二个是判断条件用了大于等于。当 ratings[i] ratings[i - 1] 时两侧评分一样没有“谁必须更多”的要求所以 left[i] 不应该更新。如果你用判断评分相等的两个孩子也会被加上一颗糖结果偏大。第三个是第二次遍历时直接覆盖 left。很多人从右到左扫完之后写出了left[i] max(left[i], right_value)这没问题但有人图省事写成left[i] right_value就把第一趟辛辛苦苦算出来的左约束覆盖没了。一旦遇到“左边上升、右边下降”的复杂波形必错。第四个是忘记取 max而是把两个数组加起来。有人可能会想“左右要求都要满足那把两个加起来不就都满足了”但这样会违反“最少糖果”的目标。正确做法是取两个下界的最大值而不是求和。用生活类比孩子既要满足妈妈的底线要求又要满足爸爸的底线要求那它需要做的不是“同时做两遍”而是“做到两者里更高的那个要求”。第五个是边界条件没考虑 n1。只有一个孩子时直接返回 1。数组版本代码自然能处理这个问题但如果你在循环里写死了 i1 到 n-1n1 时会漏掉累加答案变成 0。5.2 跳跃游戏2 的三个隐蔽错误跳跃游戏2 代码短错误隐蔽。第一个是把 farthest 计算成nums[i]而不是i nums[i]。注意nums[i] 表示“从当前位置能跳多远”位置本身有一个初始下标 i所以能到达的最远下标是 i nums[i]。漏掉 i结果在接近数组末尾时一定出错。第二个是把起跳条件写错。有些版本会在每个位置都执行jumps这是错的。只有遍历到当前覆盖区间的右边界 end 时才说明“当前这一跳已经用到极限必须起跳下一跳了”。第三个是循环边界。前面提过只需要遍历到 n-2因为最后一个位置是终点不需要再起跳。如果遍历到 n-1当 i 等于 end 且 end 恰好是最后一个位置时jumps 还会再多加一次。5.3 一套自测用例清单我平时刷题有个习惯写完代码先用一批边界用例自测再提交。糖果题的自测清单大致这样用例期望输出原因[1]1只有一个孩子[1, 2]32 1分配为 1、2[2, 1]32 1分配为 2、1[1, 1]2评分相等各 1 颗[1, 2, 3, 4]10严格递增1234[4, 3, 2, 1]10严格递减4321[1, 3, 2, 1]7先升后降峰值抬高[1, 3, 2, 2]5下降后遇相等波形中断测试时我建议把每个例子都手动推一遍数组不要只看输出正确就跳过。特别是 [1, 3, 2, 1] 和 [1, 3, 2, 2] 这两个它们能帮你验证取 max 的时机和 O(1) 版的 dec/inc 特判。6. 变种与扩展拿到新题怎么判断能不能贪心6.1 环形糖果分发破环成链的套路把糖果题改一版孩子围成一圈首尾也算相邻评分高的孩子要拿更多糖其他条件不变。这题就不能直接套两次遍历了因为数组首尾之间多了一条约束。一个比较直觉的做法是“枚举起点”先找到评分最低的孩子作为链条的起点。评分最低的孩子一定只拿 1 颗糖因为它不可能比任何邻居评分高。从它开始把环形数组“剪开”成一条链再用两次遍历的标准流程求解。这个思路建立在“最低分孩子的位置最优确定”之上破环点选得好可以把环上的约束转换成链上约束。严格地说环形版本的最优解需要额外证明某个最低分值位置一定能作为破环点面试时能讲出这个思路就已经比大部分候选人强了。真要写全往往用 O(n^2) 的枚举法兜底或者用单调性推导一个 O(n) 的解法复杂度很高不适合作为贪心入门题。我的建议是面试被追问环形变体时先讲破环为链的核心思想再给出枚举写法的复杂度分析一般就能过关。6.2 看着像贪心但实际不能贪心的反例“相邻比较”类问题里有相当多适合用动态规划而不是贪心。糖果题能贪心是因为每个位置的更新只依赖相邻一个位置且两个方向约束可以拆开。但如果你把约束改成“每个孩子要同时跟它前后两个邻居都严格比较”或者“评分差超过 2 时糖果差也要超过 2”问题就瞬间变成更复杂的约束优化贪心策略不再成立。另一个很经典的反例是零钱兑换。目标金额和不同面额之间局部最优先用最大面额可能在很多普通面额组合里不是全局最优。这不是因为贪心“不够努力”而是因为这类问题的状态空间存在后效性你选了 11 元硬币以后剩下的金额结构和你最初面对的结构性质不同不能简单递归套用同一个策略。所以看到“最少/最多/最大/最小”这类词不要条件反射就用贪心。先问一句局部最优叠加起来会不会在某个节点被迫用局部次优来补偿如果有这个可能多半需要动态规划。6.3 我的贪心题排查清单我现在拿到一道新题判断能不能用贪心基本按下面这套流程走第一目标函数是不是“某种总量最优”是的话才有贪心的探讨空间。第二约束是不是局部的糖果题约束在相邻两两之间跳跃游戏2约束在区间覆盖内这类局部约束问题才有“局部决策全局成立”的可能性。第三能不能找到反例试着构造一个“局部最优导致全局失败”的例子如果短时间内构造不出来再考虑用贪心。第四如果需要严格证明能不能用“交换论证”或者“下界论证”糖果题适合用下界论证左边下界、右边下界都满足时取 max 就是最小合法解。跳跃游戏2适合用归纳证明第 k 跳覆盖范围不会超过贪心策略覆盖的范围。把这四条过一遍能过滤掉大多数无效的贪心尝试。如果最后发现不能用贪心再切动态规划或二分搜索也不迟。我个人刷了这么多贪心题之后最大的体会是贪心算法真正的难点从来不是代码而是“判断它能不能用”和“想明白为什么局部最优就是全局最优”。糖果这道题之所以经典就是因为它把这两点都体现得特别清楚——双向约束该怎么拆、两个下界该怎么合并、为什么合并之后就是最优解每一步都有扎实的推导支撑。建议你把这个思路吃透以后见到任何“相邻比较 最优化”的题目都能第一时间想到拆方向、取下界、合并答案这条标准路线。