1. 项目概述从“分糖果”到“贪心策略”的实战演练最近在整理一些经典的算法面试题和教学案例时又翻出了“糖果分配”这个问题。这题目听起来挺生活化的不就是给一群孩子分糖嘛但它在力扣LeetCode上可是标着“困难”标签的135号题。很多刚开始接触贪心算法的朋友包括我当年都容易在这里栽跟头——思路好像有但一写就错边界条件处理得乱七八糟。今天我就想结合自己踩过的坑用C来彻底拆解一下这个问题不光是给出代码更重要的是把贪心算法在这里“为什么要用两次遍历”、“为什么局部最优能导致全局最优”的逻辑给捋清楚。如果你正在准备C面试或者想巩固一下对贪心算法的理解这篇实战笔记应该能给你提供一条清晰的路径。简单来说问题是这样有一群孩子每个孩子有一个评分值。你要根据这些评分来分配糖果规则有两条第一每个孩子至少分到1颗糖第二评分更高的孩子必须比他相邻的、评分低的孩子拿到更多的糖果。你需要用最少的糖果总数来满足这个条件。举个例子孩子评分是[1, 3, 2, 2, 1]你怎么分直觉上评分高的多分但相邻关系会让事情变复杂。直接暴力枚举所有分配方案在数据量大时是不可能的这就需要我们寻找更聪明的策略也就是贪心算法。2. 问题核心与贪心策略的抉择2.1 规则拆解与难点分析首先我们把规则翻译成更精确的编程语言描述。给定一个整数数组ratings长度为n我们需要返回一个整数sum代表最少需要的糖果总数。约束条件如下每个孩子至少得到1颗糖candy[i] 1。如果ratings[i] ratings[i-1]那么candy[i] candy[i-1]。如果ratings[i] ratings[i1]那么candy[i] candy[i1]。难点在于一个孩子的糖果数同时受到其左右邻居的影响。比如在序列[1, 3, 2]中中间评分3的孩子既要大于左边的1又要大于右边的2。你不能只盯着一边看。如果只从左到右遍历保证每个孩子比左边评分高的孩子糖多那么对于[1, 3, 2]你会得到糖果数[1, 2, 1]。这时中间的孩子3分有2颗糖右边的孩子2分有1颗糖满足了中间孩子大于左边的规则。但是中间孩子3分的评分高于右边孩子2分按照规则他的糖也应该比右边多。在[1, 2, 1]这个分配里2 1恰好也满足了所以这个例子是幸运的。但考虑[1, 2, 87, 87, 87, 2, 1]这个序列如果只从左到右贪心会得到[1, 2, 3, 1, 1, 1, 1]这显然错了因为第三个87分的孩子糖数3并不大于第四个87分的孩子糖数1尽管他们评分相同规则只要求评分高的要多评分相同则无要求所以这里第三个孩子的糖数应该至少等于第四个但我们的分配导致了减少这破坏了从左到右的递增关系。实际上更典型的错误案例是[1, 2, 3, 1]从左到右贪心得到[1, 2, 3, 1]但第三个孩子3分的糖果数3并不大于第四个孩子1分的糖果数1这违反了规则。所以单向遍历无法同时满足左右两边的不等式约束。这就是问题的核心矛盾。2.2 为什么选择“两次遍历”的贪心法既然一次遍历搞不定一个自然的想法是能不能先保证一边的规则再去调整以满足另一边的规则贪心算法在这里的体现就是将全局问题分解为两个独立的子问题分别求局部最优解然后合并。左规则当ratings[i] ratings[i-1]时candy[i] candy[i-1] 1。这保证了每个孩子相对于其左边邻居的规则。右规则当ratings[i] ratings[i1]时candy[i] candy[i1] 1。这保证了每个孩子相对于其右边邻居的规则。每个孩子最终分到的糖果数必须同时满足左规则和右规则。那么最少的糖果数怎么来对于每个孩子我们分别从左到右贪心地计算满足左规则的最小糖果数再从右到左贪心地计算满足右规则的最小糖果数。然后对于每个位置我们取这两个值的最大值。为什么是最大值因为取最大值才能同时满足两个规则如果取小了可能会违反其中一个规则。而取最大值则能确保两个规则都得到满足并且是在满足条件下的最小值因为每个方向的计算都是贪心地给最小值。这就是“两次遍历取最大值”的贪心策略。它巧妙地将双向约束分解为两个单向约束分别用贪心求解再合并。其正确性基于贪心选择性质每个子问题左规则或右规则的局部最优解当前孩子在该方向上的最少糖果数能导向全局最优解该孩子同时满足两边规则的最少糖果数。这一点可以通过反证法来理解如果存在一个更优的全局解那么至少有一个孩子在这个解中的糖果数比我们“取最大值”得到的数还要少。假设这个孩子是i如果他的糖果数比从左规则算出的值还少那就违反了左规则如果比从右规则算出的值还少那就违反了右规则。因此不存在这样的更优解。注意这里容易混淆“评分更高”和“糖果更多”的关系。规则是评分高的孩子糖果必须更多但评分相同则没有要求。因此在贪心递推时我们只在ratings[i] ratings[i-1]时才增加糖果数相等时则不做增加保持至少1的基数这是正确的。3. 算法实现与代码逐行解析理论说清楚了我们来看C实现。我会提供两个版本的代码一个是最清晰直观的标准实现另一个是稍作优化的空间优化版本。我们先从标准版开始。3.1 标准实现清晰优先#include vector #include algorithm // 用于std::max #include numeric // 用于std::accumulate class Solution { public: int candy(std::vectorint ratings) { int n ratings.size(); if (n 2) { return n; // 0个孩子返回01个孩子返回1 } // 1. 初始化糖果数组每个孩子至少1颗糖 std::vectorint candies(n, 1); // 2. 从左到右遍历满足左规则 for (int i 1; i n; i) { if (ratings[i] ratings[i - 1]) { candies[i] candies[i - 1] 1; } // 如果 ratings[i] ratings[i-1]则 candies[i] 保持为1目前 } // 3. 从右到左遍历满足右规则并取最大值 for (int i n - 2; i 0; --i) { if (ratings[i] ratings[i 1]) { // 关键取最大值以确保同时满足左规则和右规则 candies[i] std::max(candies[i], candies[i 1] 1); } // 如果 ratings[i] ratings[i1]则 candies[i] 保持不变可能已被左规则赋值 } // 4. 求和并返回 return std::accumulate(candies.begin(), candies.end(), 0); } };逐行解析与关键点边界处理if (n 2) return n;这是必不可少的。当没有孩子或只有一个孩子时不需要复杂的逻辑直接返回n。这避免了后续对空数组或单元素数组的无效访问也使逻辑更完备。初始化std::vectorint candies(n, 1);我们创建一个与评分数组等长的糖果数组并全部初始化为1。这直接满足了“每个孩子至少1颗糖”的第一个规则。后续的所有操作都是在这个基础上增加。第一次遍历左-右for (int i 1; i n; i)从第二个孩子开始索引1因为第一个孩子索引0没有左边的邻居。if (ratings[i] ratings[i - 1])这是核心判断只有当前孩子的评分严格大于左边孩子时我们才需要给他更多糖。candies[i] candies[i - 1] 1;贪心策略在满足左规则的前提下给当前孩子尽可能少的糖即只比左边孩子多1颗。这保证了从左规则角度看糖果数是最少的递增序列。如果评分不大于左边小于或等于我们什么都不做candies[i]保持为1。这里尤其要注意评分相等的情况规则没有要求评分相同者糖果数要有差异所以保持1或后续可能被右规则增加是完全正确的。第二次遍历右-左for (int i n - 2; i 0; --i)从倒数第二个孩子开始索引n-2因为最后一个孩子索引n-1没有右边的邻居。if (ratings[i] ratings[i 1])判断当前孩子评分是否严格大于右边孩子。candies[i] std::max(candies[i], candies[i 1] 1);这是整个算法的灵魂所在。candies[i 1] 1是从右规则角度看当前孩子所需的最少糖果数比右边孩子多1颗。candies[i]是经过第一次遍历后当前孩子已有的糖果数满足左规则的最少糖果数。std::max取两者中的较大值。为什么如果candies[i]更大说明左规则要求更高已经满足了右规则因为左规则值已经大于等于右规则要求值保持原值即可。如果candies[i 1] 1更大说明右规则要求更高我们需要更新candies[i]来满足右规则。同时这个新值也一定满足左规则吗是的因为第一次遍历后candies[i]至少是1而更新后的值更大所以对于其左边的孩子索引i-1如果ratings[i-1] ratings[i]在后续遍历到i-1时会通过std::max来保证i-1的糖果数大于更新后的candies[i]。如果ratings[i-1] ratings[i]则左规则本身不要求candies[i-1] candies[i]所以更没问题。求和std::accumulate(candies.begin(), candies.end(), 0)是C标准库提供的求和函数简洁高效。你也可以用简单的for循环累加。3.2 空间优化实现理解后可选标准实现用了O(n)的额外空间来存储糖果数组。我们能不能只用常数空间理论上如果只求糖果总数而不需要知道每个孩子的具体分配是可以的。但贪心算法的“两次遍历取最大值”逻辑本质上需要比较左右两次遍历的结果。有一种优化方法是利用“峰”和“谷”的概念通过单次遍历和几个变量来统计但代码会复杂很多容易出错且并不总是直观。对于面试或日常使用我强烈推荐使用标准实现。它的O(n)空间复杂度在绝大多数场景下都是完全可接受的代码的清晰度和可维护性远比节省那点空间重要。记住“过早优化是万恶之源”。先把清晰正确的逻辑写出来除非有明确的性能瓶颈否则不要追求奇技淫巧。不过为了知识完整性这里简要提一下优化思路你可以定义up、down、peak三个变量分别记录当前上升序列的长度、下降序列的长度、以及上一个峰顶的高度。在一次遍历中根据评分的变化趋势更新这些变量并计算总糖果数。但处理评分相等或序列变化时的细节非常繁琐调试困难。在面试中如果你能写出标准解法并清晰阐述已经能拿到绝大部分分数如果能提到空间优化思路并指出其复杂性则是加分项。3.3 关键参数与选择依据在这个算法中几乎没有需要手动调节的“参数”。所有的逻辑都固化在代码里。但有几个关键选择点需要理解初始化值为什么是1这是由问题最基本的约束决定的“每个孩子至少1颗糖”。这是我们的基准线。递推增量为什么是1这是贪心策略“在满足条件下给最小值”的直接体现。为了满足candy[i] candy[i-1]最小的增量就是candy[i-1] 1。给得更多比如2虽然也满足规则但就不是最小总数了。为什么第二次遍历要用std::max而不是直接赋值这是保证同时满足两个规则的核心。直接赋值candies[i] candies[i 1] 1会覆盖掉第一次遍历的结果可能破坏已经满足的左规则。取最大值是唯一的正确合并方式。遍历顺序可以互换吗可以。你可以先进行从右到左的遍历满足右规则再进行从左到右的遍历取最大值。逻辑是完全对称的。代码实现上只需交换两个循环的顺序和比较条件即可。4. 从理论到实践调试、测试与性能分析4.1 如何验证你的代码写完代码不要急着提交自己先构造几个测试用例跑一跑。这是避免“一次提交就AC”假象的好习惯。我常用的测试集包括边界案例空数组[]应返回0。单元素数组[5]应返回1。两个元素[1,2]应返回3 (分配[1,2])。两个元素[2,1]应返回3 (分配[2,1])。所有评分相同[7,7,7,7]应返回4 (每人1颗)。典型功能案例[1,0,2]应返回5 (分配[2,1,2])。这是一个小峰谷。[1,2,2]应返回4 (分配[1,2,1]或[1,2,1]注意第二个2可以和第一个2糖果数相同但为了最少给1颗)。这里容易错给成[1,2,2]。[1,3,2,2,1]应返回7 (分配[1,2,1,2,1])。自己手算一下验证。复杂案例[1,2,87,87,87,2,1]这是一个平台连续相等值接下降的案例。标准算法应正确处理。力扣的官方测试用例通常包含长序列和极端值。在本地你可以写一个简单的main函数来测试int main() { Solution sol; std::vectorint test1 {1,0,2}; std::cout Test [1,0,2]: sol.candy(test1) (expected: 5) std::endl; std::vectorint test2 {1,2,2}; std::cout Test [1,2,2]: sol.candy(test2) (expected: 4) std::endl; // ... 更多测试 return 0; }4.2 常见错误与排查技巧即使理解了算法实现时也常会掉进一些坑里。下面是我和学生们常遇到的错误清单错误现象可能原因排查与修复结果比预期少第二次遍历时直接赋值candies[i] candies[i1]1覆盖了左规则结果。改为candies[i] max(candies[i], candies[i1]1)。结果比预期多在评分相等时也进行了递增操作例如if (ratings[i] ratings[i-1])。严格使用进行比较相等时不增加。数组越界访问遍历时循环边界设置错误例如第一次遍历从i0开始访问ratings[i-1]。检查循环起始和终止索引。左遍历从1开始右遍历到倒数第二个结束。处理空数组返回1没有进行边界检查直接对空数组进行vectorint candies(n, 1)操作。在函数开头添加对n 2的判断并直接返回n。对于长平台连续相等评分分配糖果数递减贪心策略理解有误认为评分相等也要保持递增或递减趋势。牢记规则只有评分严格大于时才需要更多糖。评分相等时糖果数可以任意但至少为1为了总数最小应尽量给1颗。实操心得在纸上画图是调试贪心算法最有效的方法之一。画出一条评分曲线然后手动模拟两次遍历的过程在每个点标出第一次遍历后的糖果数和第二次遍历更新后的糖果数。视觉化能让你立刻发现max操作的必要性。4.3 复杂度分析与适用场景时间复杂度O(n)。我们进行了两次线性遍历每次遍历都只做了常数次比较和赋值操作。空间复杂度O(n)。用于存储糖果数组。如前所述这是标准的、可接受的空间开销。适用场景这种“两次遍历取最大值”的贪心模式适用于一类具有双向约束的序列分配问题。其核心特征是每个元素的值需要同时参考其左边和右边邻居的某种属性来决定并且约束是单调的如“大于”。一旦识别出这种模式就可以考虑应用此策略。5. 贪心算法的本质与解题思维训练通过这个“糖果分配”问题我们可以更深入地思考贪心算法。贪心算法不是瞎猜它通常适用于具有“贪心选择性质”和“最优子结构”的问题。在这个问题中贪心选择性质每次我们给一个孩子分配满足单边规则的最小糖果数左规则或右规则这个局部选择是安全的不会影响后续全局最优解。最优子结构整个问题的最优解总糖果数最少包含了其子问题满足左规则的最少序列、满足右规则的最少序列的最优解。如何培养用贪心法解题的思维识别贪心标志问题求的是“最小”或“最大”而且决策是序列化的每一步的选择似乎只影响临近元素。尝试提出贪心策略先考虑一个方向比如从左到右制定一个简单的规则如如果比左边大就比左边多1。验证策略的正确性这是最关键也最难的一步。常用的方法有反证法假设存在一个更优解看能否推出矛盾。交换论证通过交换解中的某些元素证明贪心解不会更差。对于“糖果分配”这类问题“分解-合并”的思路分解为两个单向问题是一个很强的提示。考虑边界和特殊情况空数组、单元素、全部相等、严格递增/递减序列等。用测试用例验证在脑子里或纸上跑几个例子尤其是那些你觉得可能出错的“拐点”案例。最后关于C实现的一些细节使用std::vector是动态数组的最佳选择。std::accumulate求和既简洁又高效通常会被编译器优化。在算法竞赛或面试中这类代码的简洁性和正确性远比微小的性能差异重要。确保你的代码清晰易读变量命名合理如ratings,candies并加上必要的注释尤其是在处理像std::max这样的关键操作时。