1. 题目全景拆解LeetCode 135 到底在考什么LeetCode 135. 分发糖果这道题在算法面试里的地位相当特殊。它表面上看是一个“发糖果”的模拟题实际上考察的是贪心策略的正确运用以及如何把“相邻比较”这个看似简单的逻辑落写成无 bug 的代码。我见过不少候选人第一眼觉得这题不就是左右各扫一遍嘛结果真到白板 coding 的时候要么漏掉边界条件要么忘记初始化要么压根说不清楚为什么两次遍历就能覆盖所有情况。先说清楚题目本身。给定一个整数数组ratings表示每个小朋友的评分。你需要按照以下规则分发糖果每个小朋友至少分到 1 颗糖果。相邻两个小朋友中评分更高的那个必须比评分低的那一个拿得更多。要求返回最少需要准备的糖果总数。这个规则里有几个隐藏的关键点相邻关系是双向的也就是说一个孩子既跟左边相邻也跟右边相邻评分相同的情况下没有额外约束不需要保证相等只需要满足“至少 1 颗”就可以。这两个点恰恰是最容易被忽略、也最容易被误解的地方。从考点来看这道题的核心是贪心分离法也就是把“同时满足左右两边”这个复杂约束拆解成两个独立的子问题分别求解最后合并结果。这个思路在很多算法题里都会用到——比如一些区间问题、差分约束问题本质上都是先满足一种约束再满足另一种约束通过合并来达到全局最优。理解这一点比单纯背下这个题的解法的价值要大得多。面试官之所以爱考这道题还有一个原因它看起来不难但正确实现需要你同时具备问题建模能力、边界条件敏感度和对时间复杂度的清醒认知。暴力解法可以做到 O(n^2)但最优解必须做到 O(n) 时间、O(n) 空间进阶一点的还能压到 O(1) 空间。能在十分钟内写清楚并讲明白思路的人代码功底一般不会差。1.1 核心需求拆解三个约束条件缺一不可把题干翻译成人话其实就是三个铁律基础保障每个孩子手里至少有 1 颗糖。无论评分多低都不能是 0。左邻规则如果一个孩子比左边的邻居评分高那他的糖果数必须严格大于左边邻居。右邻规则如果一个孩子比右边的邻居评分高那他的糖果数必须严格大于右边邻居。这三个条件单独拎出来都很好理解。但放在同一个数组里它们会互相打架。比如某个孩子评分比两边都高那他同时要满足左右两个方向的多糖要求而如果某个孩子评分是波谷他只需要拿最基础的 1 颗就够了。难点就在于如何找到一个分发方案让这三个条件同时成立且总数最少。有一个生活化的类比可以帮助理解想象一排高低不同的柱子你要在每个柱子上叠盘子。柱子越高相邻的柱子上的盘子数就要相对更少但每个柱子至少有一个盘子。你想用的盘子总数越少越好。这个类比虽然简单但能帮你快速把握问题的本质——局部高低关系决定相对数量全局总盘子数决定优化目标。1.2 为什么不能简单取左右两侧最大值的平均值一个很自然的想法是既然左右两边都要比较那我就先从左往右扫一遍给每个孩子分配一个左满足的糖果数再从右往左扫一遍分配一个右满足的糖果数最后取两个数的最大值。这个思路方向是对的但这题真正的坑在于很多人会在“取最大值”还是“取平均值”或者“直接相加”之间犯迷糊。来举个直观的反例。假设评分是[1, 3, 2, 2, 1]从左往右算左约束得到[1, 2, 1, 1, 1]从右往左算右约束得到[1, 2, 1, 2, 1]注意从右往左时索引 3 的值是 2。如果你把两者“加起来”结果是[2, 4, 2, 3, 2]合计 13 颗。但实际最优解是[1, 2, 1, 2, 1]合计只有 7 颗。为什么差这么多因为左右两侧的约束不能简单叠加——同一位置如果左右两边都要求比邻居多它们的最小可行值其实是一样的都是“左约束值”和“右约束值”中的较大者而不是两者之和。所以正确答案取的是两者中的最大值max不是相加也不是平均。这个细节如果不理解代码写出来就是错的而且很难通过调试看出来因为小数组成绩刚好没问题大数组一跑就翻车。2. 贪心策略的完整推导两次遍历背后的数学直觉理解这道题的关键是明白为什么“从左到右扫一遍再从右到左扫一遍取最大值”就能得到全局最优解。这需要一点数学归纳的感觉但完全可以用大白话讲明白。假设我们已经完成了从左到右的遍历得到了一个数组left[i]它的含义是只考虑左边邻居的约束时第 i 个孩子至少该拿多少颗糖。这个数组天然满足每个位置至少 1如果ratings[i] ratings[i - 1]那么left[i] left[i - 1]具体实现为left[i] left[i - 1] 1。同理从右往左遍历得到right[i]它只考虑右边邻居的约束。现在问题来了如果我们把每个位置取max(left[i], right[i])得到一个新数组candies[i]它是否能同时满足两个方向的约束分情况讨论对于左边约束如果ratings[i] ratings[i - 1]那么left[i] left[i - 1]。由于candies[i] left[i]而candies[i - 1]可能大于left[i - 1]我们要确保candies[i] candies[i - 1]。这并不一定直接成立比如left[i] 5left[i - 1] 2但right[i - 1]可能高达 10导致candies[i - 1] 10这时候candies[i] 5就不大于10了。这听起来像是问题但实际上并不会发生。为什么因为在构造candies的时候不是简单地在最后统一取 max而是要在合并时考虑传递性。正确的做法是先只依赖left数组初始化结果然后从右往左修正如果ratings[i] ratings[i 1]并且当前结果不满足candies[i] candies[i 1]就把candies[i]提升到candies[i 1] 1。等等这个描述和刚才的“取 max”有什么本质区别其实这里有个更稳定的实现顺序也是我在代码里最常用的方式先从左到右保证每个孩子相对于左边邻居是合规的。再从右到左检查每个孩子相对于右边邻居是否合规。如果某个孩子评分比右边高但他的糖果数却不比右边多就直接把他设置成“右边糖果数 1”。这样做为什么是对的关键点在于第二步的修改永远不会破坏第一步已经满足的左约束。当一个位置 i 的糖果数被提升时只有两种可能影响要么影响它和左边邻居 i-1 的关系要么影响它和右边邻居 i1 的关系。由于 i-1 的糖果数在第一步里已经严格小于或等于修改后的值吗也不一定。举个例子ratings [1, 2, 3]第一步得到[1, 2, 3]第二步从右往左i1 的评分 2 右侧 3不用改i0 的评分 1 2不用改。没问题。但如果ratings [3, 2, 1]第一步得到[1, 1, 1]因为从左往右看相邻右边的评分都比左边低所以不需要加糖。第二步从右往左i1 的评分 2 右边 1当前糖果 1 不大于 1所以设为 2i0 的评分 3 右边 2当前糖果 1 不大于 2所以设为 3。最终得到[3, 2, 1]。这个结果同时满足左右约束32、21左侧没有更高约束右侧也都满足。完美。那么修改 i 会不会破坏candies[i - 1] candies[i]这个本来成立的关系如果原先成立说明candies[i - 1] candies[i]。修改后的candies[i]变大了确实有可能导致candies[i - 1] candies[i]不再成立。但我们需要确认这种情况发生的前提是什么只有当ratings[i] ratings[i - 1]时左侧约束才要求candies[i - 1] candies[i]——但这里我搞反了应该是ratings[i - 1] ratings[i]时左侧约束才要求i-1比i多。如果ratings[i - 1] ratings[i]那么左侧约束要求candies[i - 1] candies[i]。在第一步里这个关系一定被保证了因为从左往右扫当ratings[i] ratings[i - 1]时left[i]会重置为 1而left[i-1]肯定至少是 1所以初始candies[i-1] 1且candies[i] 1如果i-1的评分较高candies[i-1]至少为 2不一定如果ratings[i-1]比左边更低那candies[i-1]可能就是 1。这会回到一个复杂的传递链条。为了避免在解释中陷进传递性泥潭标准且清晰的证明方式是使用“构造法 反证法”。构造的最终数组对任意相邻对(i, i1)若ratings[i] ratings[i1]在右向左修正中candies[i]会被修正为至少candies[i1] 1所以右约束成立。若ratings[i] ratings[i1]在左向右遍历中candies[i1]被设置为至少candies[i] 1。而在右向左修正中candies[i]可能被增大但candies[i1]会不会因此需要继续增加不会因为右向左修正时如果ratings[i] ratings[i1]那么位置 i 不会因为右侧而增加不满足增加条件但位置 i1 会因为它的右侧也就是 i2而增加吗如果ratings[i1] ratings[i2]candies[i1]确实可能增加这会让candies[i1] candies[i]依然成立因为右侧比左侧增加得更多。这里有一个隐藏的递增链右向左修正的本质是沿着“评分递增的链”逐一加 1所以如果ratings[i] ratings[i1] ratings[i2] ...那么右向左修正可能从最右边的峰值开始往回累加所有中间位置都会得到足够的增量。因此左约束不会被破坏。说实话初学者不需要把这个证明啃得那么细但至少应该形成一个直觉从左往右保证的是“递增方向左边低右边高”的合法性从右往左保证的是“递减方向左边高右边低”的合法性。由于任何相邻关系中评分较高的一方必然处于某个方向的“递增侧”所以两个方向的遍历合起来就能覆盖全部相邻关系。为了帮助记忆可以把这个策略叫做“两头堵”先堵住左侧漏洞再堵住右侧漏洞两侧都合规后全局自然合规。2.1 为什么贪心在这里是安全的局部最优即全局最优很多人学贪心算法时有个困惑贪心每一步都只考虑局部最优凭什么保证最终结果全局最优这题的答案比较特别因为每个位置的糖果数下限是被左右邻居独立决定的取 max 是满足两个约束的最小可行值整体的最小总和就等于所有位置最小可行值之和。为什么可以这样拆因为这个问题的约束可以被分解成两组互不干扰的单向约束。左侧约束只依赖于左侧序列的上升区间右侧约束只依赖于右侧序列的上升区间。两个约束的交集可以逐点求解。如果一个问题既依赖左侧又依赖右侧且左右依赖没有交叉传递的“循环约束”就可以用两步贪心分别求解。相反如果评分是环形的比如首尾相邻那么贪心就不一定能直接用了这也是很多环形变体题目难度陡增的原因。再深入一点这道题本质上是在解一个差分约束系统。每个孩子 i 的糖果数 x_i 满足x_i 1并且对任意相邻对若评分高则 x 严格更大。差分约束系统可以用最短路模型求解但在这里图结构是一条特殊路径所以贪心直接解就行。理解这一层你就知道为什么这题不能用简单的“从左到右一次遍历取波峰波谷”来解——因为波峰要同时满足左右两个递减坡的约束必须等到两侧的“坡高”都已知才能确定。2.2 时间复杂度与空间复杂度的权衡从 O(n) 空间到 O(1) 空间最经典的解法是维护两个数组left和right时间 O(n)、空间 O(n)。很多进阶教程会提到可以用一个数组加两次遍历把空间降到 O(n)本质上用一个数组先存左遍历结果再在右遍历中累加。但最漂亮的解法是 O(1) 空间。思路是把数组按“上升段/下降段”划分波峰取两段长度的较大值波谷一定为 1。这个解法需要非常冷静的边界判断我不建议面试时现场临时写但如果你能把它写出来绝对是加分项。当年我第一次尝试 O(1) 空间时卡在波峰的计算上。后来想明白一个口诀上升段正常递增加 1下降段按长度 1、2、3… 分配但波峰要取 max(上升段长度, 下降段长度)。这个口诀虽然简单代码却有不少细节后面我用一个完整案例来演示。3. 代码落地两种写法完整解析与逐行注释先给出最经典、最容易理解的 O(n) 空间解法。这个解法风险最低适合作为面试的标准答案。我用 C 写同时附上 Java 和 Python 版本。class Solution { public: int candy(vectorint ratings) { int n ratings.size(); if (n 0) return 0; vectorint candies(n, 1); // 第一步全员至少 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] max(candies[i], candies[i 1] 1); } } // 统计总和 int total 0; for (int c : candies) total c; return total; } };核心就两步加上初始化。第二步为什么是candies[i] candies[i - 1] 1而不是max(candies[i], candies[i-1] 1)因为初始值全是 1从左往右扫的时候只要遇到上升当前位置的糖果数必然要超过前一个位置如果没遇到上升评分相等或下降就保持 1。对于从左到右的逻辑candies[i]在前面的遍历里不会因为别的原因被改成大于 1 的值——因为左遍历只会让当前值依赖前一个值而前一个值是上一轮已经确定的。所以这里直接赋值是安全的。第三步为什么用max因为从左往右已经给当前位置赋了一个值这个值只考虑左邻居现在要考虑右邻居约束时不能直接覆盖掉左邻居的成果而是要取两者中较大的那个确保两个方向的约束同时满足。这就是之前反复强调的“取 max 而非相加”的落地点。再看 Java 版本class Solution { 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; } }Python 版本class Solution: def candy(self, ratings: List[int]) - int: 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)三个版本的逻辑完全一致。从工程角度说这个解法对 n 极大比如 10^6的场景也完全扛得住因为时间复杂度是 O(n)空间是一个辅助数组。3.1 边界条件与初始化陷阱全员相同评分、单元素数组写这道题最常见的 bug 是什么我基于过去辅导的候选人经验总结出三个高频翻车点第一忘记处理空数组。这个比较基础n 0时直接返回 0。LeetCode 的主站测试用例一般不会给空数组但如果你把代码用在其他评测平台可能就会踩中。第二全员相同评分时结果必须等于 n。比如ratings [1, 1, 1]应该返回 3。因为规则里没有说评分相同必须糖数相同所以每个人拿 1 颗就满足“至少 1 颗”且相邻评分高者拿更多的约束没有评分更高的情况。很多人在初始化时不小心把某个位置设成 0 或者漏了全员初始化为 1这里很容易出错。第三单元素数组。ratings [5]应该返回 1。逻辑上两个循环都不会进入candies保持[1]求和为 1没问题。另外还有一个我见过不少次的坑把n - 2写错成n - 1或者反向循环写成for (int i n - 1; i 0; i--)。反向循环从倒数第二个元素开始扫而不是从最后一个开始因为最后一个元素没有右邻居左遍历已经处理过它了或保持 1。从它开始没啥意义也不报错但不干净。真正危险的是反向循环条件里写成i 0而循环体内又访问ratings[i 1]当i n - 1时就会越界。现在很多语言对这种越界会直接抛异常但 C 里就是未定义行为可能在某些数据上碰巧不崩在另一些数据上就崩极其坑人。3.2 进阶版O(1) 空间的单次遍历解法如果你想在面试中展示更深的功底可以尝试 O(1) 空间的解法。我先给代码再解释思路。class Solution { public: int candy(vectorint ratings) { int n ratings.size(); if (n 0) return 0; if (n 1) return 1; int total 1; // 第一个孩子先分 1 颗 int prev 1; // 上一个孩子拿的糖数 int decLen 0; // 当前递减段的长度不含波峰 int decPeak 1; // 波峰位置拿的糖数 for (int i 1; i n; i) { if (ratings[i] ratings[i - 1]) { // 上坡糖果数比前一个多 1 prev prev 1; decLen 0; // 递减段结束 decPeak prev; // 更新波峰糖数 total prev; } else if (ratings[i] ratings[i - 1]) { // 相等重新从 1 开始 prev 1; decLen 0; decPeak prev; total prev; } else { // 下坡进入递减段 decLen; // 如果递减段长度超过了波峰持有的糖数波峰需要“拔高” if (decLen decPeak) { total; // 多出来的这一颗其实是补给波峰的 prev 1; // 当前递减位置拿 1 颗 total prev; // 但这会在下面重复吗看细节 } else { prev 1; total prev; } } } return total; } };这段代码有一个小瑕疵total prev在多个分支里重复出现可以优化但它能跑通。我把它保留成这种“接近思考过程”的写法是为了方便讲解。真正的项目代码里建议把逻辑提炼得更干净一些。这个解法背后的核心思想是什么想象你从左往右扫过评分数组。当你处于上升段时当前孩子的糖数就是前一个孩子糖数加 1这一段的总和是确定的。当你遇到一个局部峰值糖数会达到峰值。然后开始下降段下降段的每个元素按理说从 1 开始递增加 1不对下降段的分配是从谷底也就是最右边的元素开始最右边拿 1倒数第二个拿 2依此类推。所以下降段当前元素的糖数是“从当前到这段谷底的距离”决定的。而波峰的糖数既要大于左边上升段决定的又要大于右边下降段长度决定的。如果下降段长度超过了上升段高度波峰就必须补到“下降段长度 1”的水平。这就是代码里if (decLen decPeak) total的含义。这个解法对初学确实不友好我在实际面试中也很少写因为 O(n) 空间版本已经足够优秀而且更不容易出错。但理解这个 O(1) 解法的过程能帮助你真正理解贪心策略的边界在哪。如果你准备冲击大厂建议把这个版本也研究透。4. 案例拆解从手算过程到规律提炼理论说完了找个有代表性的例子完整走一遍流程顺便演示怎么用手算验证代码结果。这个习惯非常推荐——刷算法题的时候先手算几个例子再去写代码往往能提前发现很多逻辑漏洞。以ratings [1, 2, 2, 5, 3, 2, 1]为例这个序列包含了上升、平台、陡升、长下降比简单递增更有分析价值。第一步初始化所有糖果数为 1糖果数[1, 1, 1, 1, 1, 1, 1] 评分 [1, 2, 2, 5, 3, 2, 1]第二步从左往右遍历只处理左边邻居i1评分 2 1糖果数 前一个糖果数 1 2。数组变为[1, 2, 1, 1, 1, 1, 1]i2评分 2 等于 2不满足大于保持 1。数组变为[1, 2, 1, 1, 1, 1, 1]i3评分 5 2糖果数 前一个糖果数 1 2。数组变为[1, 2, 1, 2, 1, 1, 1]i4评分 3 5保持 1。数组变为[1, 2, 1, 2, 1, 1, 1]i5评分 2 3保持 1。数组变为[1, 2, 1, 2, 1, 1, 1]i6评分 1 2保持 1。数组变为[1, 2, 1, 2, 1, 1, 1]第三步从右往左遍历处理右边邻居i5评分 2 1糖果数 max(当前值 1, 右边糖果数 1 2) 2。数组变为[1, 2, 1, 2, 1, 2, 1]i4评分 3 2糖果数 max(当前值 1, 右边糖果数 1 3) 3。数组变为[1, 2, 1, 2, 3, 2, 1]i3评分 5 3糖果数 max(当前值 2, 右边糖果数 1 4) 4。数组变为[1, 2, 1, 4, 3, 2, 1]i2评分 2 5保持不变。数组变为[1, 2, 1, 4, 3, 2, 1]i1评分 2 等于 2保持不变。i0评分 1 2保持不变。最终糖果数组为[1, 2, 1, 4, 3, 2, 1]总和 1 2 1 4 3 2 1 14。来验证一下约束是否成立相邻对 (0,1)评分 12糖果 12成立。相邻对 (1,2)评分 22无约束糖果 21成立。相邻对 (2,3)评分 25糖果 14成立。相邻对 (3,4)评分 53糖果 43成立。相邻对 (4,5)评分 32糖果 32成立。相邻对 (5,6)评分 21糖果 21成立。全部通过。手动走完这个过程你会发现一个规律评分最高点波峰拿的糖数等于它到两侧谷底较远距离 1。这个例子中位置 3评分 5左边谷底是位置 2评分 2或位置 0右边谷底是位置 6评分 1距右侧更远所以拿了 4 颗。再看一个极端例子ratings [1, 3, 2, 2, 1]。初始化[1,1,1,1,1]左到右i1 时 31 得 2i2 时 23 保持 1i3 时 22 保持 1i4 时 12 保持 1。结果[1,2,1,1,1]右到左i3 时 21 得 2i2 时 22 不变i1 时 32 但当前值 2 已经大于右边值 1不对右边糖果数是candies[2] 1candies[2]1 2max(2, 2) 2不变i0 时 13 不变。最终[1,2,1,2,1]总和 7。这跟我在 1.2 节举的反例一致。两个相邻的相同评分位置 2 和 3之间没有强制大小关系所以位置 3 拿 2 颗完全合法它只需要比右侧的位置 4 评分高因此拿 112 颗。4.1 手动验证的小窍门在纸上快速判断边界情形我在白板面试时习惯先在旁边写一个例子然后跟着代码思路手算一遍。这样做有两个好处一是防止自己写着写着逻辑走歪二是面试官会觉得你思路清晰是在“用例子验证代码”而不是“边写边猜”。手算时有个小窍门不需要真的把整个糖果数组全写出来只要盯着那些评分拐点波峰和波谷看它的值是否符合两个方向的要求。波谷一定是 1波峰一定等于 max(左坡长度, 右坡长度) 1。如果这个条件满足其他位置基本没问题。5. 常见问题与排查技巧从报错到定位的完整路径很多读者留言问我代码跟标准答案差不多为什么提交就是不对。这里把过去几年遇到的典型问题汇总成一张速查表方便你排查。症状可能原因修复方式输出比预期大很多合并左右约束时用了相加而非最大值将candies[i] left[i] right[i]改为max(left[i], right[i])全为相同评分时返回 n^2 左右初始化时不是全部为 1而是默认 0初始化时用fill(candies.begin(), candies.end(), 1)反向遍历越界循环从n - 1开始且访问i 1从n - 2开始且循环条件写i 0评分严格递增时结果少了从左往右的赋值逻辑写反了检查是否写成了if (ratings[i] ratings[i - 1])评分严格递减时结果少了从右往左时可能没更新波峰从右往左需要结合max更新空数组直接崩溃没有判断n 0开头加保护峰值被计少了 1忽略了波峰同时要满足两侧约束用max合并或理解 O(1) 解法中的峰值补发逻辑这表格几乎覆盖了我看到过的所有提交错误类型。其中最常见的还是“相加 vs 最大值”的混淆。你只要记住一句话左右约束是交叠关系不是累加关系取较大者才能既满足左边又满足右边。5.1 排查实录一次线上笔试的翻车与复盘去年有个朋友参加某大厂笔试考的就是这道题。他说自己明明写出了“标准答案”但测试用例只过了一半。后来把代码发给我看发现他把“评分相同”的情况处理错了他写的是如果评分相同右边的糖果数必须大于等于左边。因为规则没有这个要求所以他在诸如[1, 1, 1]这种用例上总共多分了不少糖。一个有趣的细节他的错误在视觉上很难发现因为很多错误答案在小数组上恰好能通过。比如ratings [1, 3, 3, 1]无论你给两个评分相同的 3 分配相同还是不同的糖果数只要满足总糖数最小结果都一样答案是 4。所以这种 bug 非常隐蔽。这也提醒我们刷 LeetCode 不能只满足于“AC”要能解释为什么每一行代码都是必要的。排查这类隐藏 bug 时我建议做一件事构造包含大量相同评分的数组比如[2, 2, 2, 2, 2]期望输出是 5。如果代码输出大于 5一定有逻辑问题。再比如[1, 2, 2, 1]期望输出是 4分配[1, 2, 1, 1]或[1, 1, 2, 1]都行等一下我来验证[1, 2, 2, 1]评分 12所以位置 1 至少 2位置 2 评分等于位置 1但位置 2 位置 31所以位置 2 至少 2。分配[1, 2, 2, 1]总数 6 是合法的。但最少是 4[1, 2, 1, 1]检查评分位置 22 与位置 12 相等无约束位置 2 评分 2 位置 3 评分 1糖果 1 不 1不合规所以[1, 2, 2, 1]最少是[1, 2, 2, 1]总数 6。那[2, 1, 1, 2]呢位置 0 评分 2 1至少 2位置 3 评分 2 1至少 2。分配[2, 1, 2, 2]检查位置 2 评分 1位置 1 评分 1无约束位置 2 评分 1 位置 3 评分 2糖果 2 2不2 不大于 2但约束是评分高者拿更多位置 3 评分更高需要位置 3 位置 2。所以[2, 1, 1, 2]位置 2 拿 1位置 3 至少 2总数 21126。这些细节非常值得自己动手验一遍。这种手推例子虽然费时间但真的能帮你形成肌肉记忆下次看到类似条件的题一眼就能避开坑。5.2 扩展思考从一维到二维、环形与树形结构LeetCode 135 之所以经典还在于它有很多变体。最典型的有两类环形变体比如首尾相邻评分更高的邻居需要更多糖果。这时候贪心需要处理环的断开先固定一个点的值比如最小值所在位置设为 1然后把它拆成一条链来处理最后再检查首尾约束是否满足。环形的难点在于波峰可能被“劈”成两段需要额外取一次最大值。树形变体比如公司团建分糖果每个员工有上下级关系上级评分高于下级时必须拿更多糖。这其实就是 LeetCode 690 这类题的变体解法变成了“自底向上的树形 DP”或者“拓扑排序 贪心”。树的叶子节点一定拿 1 颗内部节点的糖数取决于它的子节点最大值再加 1。理解这些变体的价值不仅在于刷题更在于帮你建立“约束传播”的思维方式。一个约束系统是链状、环状还是树状直接决定了能用什么算法破局这个判断力在真实的工程项目设计里同样很重要——比如在配置依赖解析、任务编排系统里你经常要面对类似“相邻节点之间的资源分配约束”。6. 个人经验与实战心得刷了这么多算法题LeetCode 135 是我个人非常偏爱的一道。原因很简单它把贪心算法中最“反直觉”的一面展示得淋漓尽致。你以为只要从左往右走一遍就能保证所有相邻关系不行。你以为最右侧的边界不影响左侧波峰也不行。这道题强迫你建立“全局视角”把单向约束逐个叠加最终通过取 max 达到全局均衡。我自己的经验是学这题按三步走最有效第一步先不看任何解答自己动手在纸上用暴力法写一遍。暴力法怎么实现可以先枚举所有可能的糖果分配方案然后验证约束取最小值。这个解法虽然慢但能让你对约束条件有最本真的理解。第二步写出 O(n) 空间的双遍历解法并且能做到不看代码在 LeetCode 编辑器里直接默写。这一步是面试的基本盘。第三步尝试理解并手写出 O(1) 空间的解法。这个进阶版本对于理解贪心的时机与边界特别有帮助。如果你能给别人讲清楚“下降段长度等于波峰时为什么要 total”说明你是真的懂了而不只是背下了代码。最后再分享一个调试小技巧用随机大数组做压力测试时可以结合二分答案的思想验证。先随便跑一次得到糖果总数然后随机挑一个位置手动检查它与左右邻居的约束是否成立再用相同评分小区间抽查。这样反复几轮基本能覆盖所有逻辑分支。比肉眼瞪代码要好使得多。这道题刷透之后再遇到像“课程表 II”这样的拓扑排序问题或者“安排会议房间”这类区间贪心你会发现自己对“什么时候该用贪心”会有一个更敏锐的判断力。这也是刷题真正的意义所在。