1. 问题背景与核心挑战LeetCode 135题分发糖果是一个经典的贪心算法应用题它模拟了现实中的资源分配场景。题目描述为N个孩子站成一排每个孩子有一个评分值。你需要按照以下要求给这些孩子分发糖果每个孩子至少分配到1个糖果评分更高的孩子必须比相邻的孩子获得更多的糖果这个看似简单的问题背后隐藏着两个关键约束条件左约束当前孩子如果比左边孩子评分高则糖果数必须多于左边右约束当前孩子如果比右边孩子评分高则糖果数必须多于右边这两个约束条件形成了典型的双向约束问题也是这个题目的核心难点所在。我们需要找到一个同时满足这两个约束条件的糖果分配方案并且使总糖果数最小。2. 贪心算法解题思路解析2.1 贪心算法的适用性分析贪心算法特别适合这类具有局部最优性质的问题。在这个题目中每个孩子的糖果分配只需要考虑其与直接相邻孩子的关系不需要考虑更远的孩子。这种局部性质使得我们可以分步骤、分阶段地解决问题。贪心选择性质体现在为了满足总糖果数最小每个孩子应该尽可能被分配最少的糖果即在满足约束条件下取最小值。这种局部最优的选择最终会导致全局最优解。2.2 双向处理策略解决这个问题的关键在于如何处理双向约束。一个有效的策略是将问题分解为两个单向处理从左到右遍历只考虑每个孩子与其左边孩子的关系从右到左遍历只考虑每个孩子与其右边孩子的关系然后对于每个孩子取两次遍历结果中的较大值作为最终分配的糖果数。这样可以确保同时满足两个方向的约束。3. 详细实现步骤3.1 初始化阶段首先我们初始化一个长度为n的数组candy其中n是孩子的数量。初始时每个孩子至少分配1个糖果n len(ratings) candy [1] * n3.2 从左到右遍历处理左约束我们首先处理左约束即确保每个孩子如果比左边孩子评分高则糖果数也更多for i in range(1, n): if ratings[i] ratings[i-1]: candy[i] candy[i-1] 1这个遍历保证了对于任意i如果ratings[i] ratings[i-1]那么candy[i] candy[i-1]。3.3 从右到左遍历处理右约束接下来处理右约束即确保每个孩子如果比右边孩子评分高则糖果数也更多。这里需要注意我们需要取当前值和右边值加1中的较大值for i in range(n-2, -1, -1): if ratings[i] ratings[i1]: candy[i] max(candy[i], candy[i1] 1)这个遍历保证了对于任意i如果ratings[i] ratings[i1]那么candy[i] candy[i1]。3.4 计算总糖果数最后我们只需要将所有分配的糖果数相加即可total sum(candy)4. 算法正确性证明4.1 约束满足性通过两次遍历我们确保了从左到右遍历后所有左约束被满足从右到左遍历后所有右约束被满足因为取max操作不会破坏已经满足的左约束因此最终的分配方案同时满足两个方向的约束。4.2 最小性证明要证明这个方案使用的总糖果数是最小的可以考虑每个孩子最终分配的糖果数是满足其左右约束所需的最小值任何试图减少某个孩子糖果数的尝试都会违反至少一个约束条件因此这个方案确实实现了总糖果数的最小化。5. 复杂度分析时间复杂度O(n)因为我们只进行了两次线性遍历空间复杂度O(n)用于存储糖果分配结果这是最优的复杂度因为任何解决方案至少需要O(n)时间读取输入和O(n)空间存储结果。6. 边界情况与特殊测试用例6.1 单调递增序列输入[1,2,3,4,5] 输出15分配[1,2,3,4,5] 说明这种情况下糖果分配完全跟随评分增长6.2 单调递减序列输入[5,4,3,2,1] 输出15分配[5,4,3,2,1] 说明与递增序列类似但需要从右向左处理6.3 平台序列相等评分输入[1,2,2,2,1] 输出7分配[1,2,1,2,1] 说明相等的评分不要求糖果数相同但要注意不能违反相邻约束6.4 单元素序列输入[5] 输出1 说明只有一个孩子时只需分配1个糖果7. 常见错误与调试技巧7.1 错误仅单向遍历只进行从左到右或从右到左的单向遍历会导致另一侧的约束不被满足。例如对于[1,3,4,5,2]如果只从左到右遍历最后一个2会只分配1个糖果但实际需要分配2个因为比右边的...哦这是最后一个实际上这个例子不太恰当更合适的例子是[1,2,87,87,87,2,1]仅从左到右[1,2,3,1,1,1,1] → 不满足右约束仅从右到左[1,1,1,1,2,1,1] → 不满足左约束正确结果[1,2,3,1,3,2,1]7.2 错误在从右到左遍历时不取max如果从右到左遍历时简单地执行candy[i] candy[i1]1会破坏已经建立的左约束。例如对于[1,2,3,1]从左到右后[1,2,3,1]如果从右到左不加max[1,2,2,1] → 第二个3会被错误地减少正确做法保持3不变7.3 调试技巧当遇到错误时可以打印每次遍历后的糖果分配数组检查每个位置的分配是否满足其与相邻位置的约束特别注意评分相等的情况确保没有不必要的增加8. 算法优化与变种思考8.1 空间优化如果允许修改输入数组我们可以利用输入数组的一部分空间来存储中间结果将空间复杂度降低到O(1)。但在实际面试中通常不需要这样做清晰比微优化更重要。8.2 变种问题环形排列如果孩子们是围成一个圈即第一个和最后一个也相邻问题会变得更加复杂。这种情况下我们需要找到评分最小的孩子从那里开始分配或者将环形问题转换为线性问题处理8.3 变种问题不同约束条件如果约束条件变化比如评分相等的孩子必须得到相同数量的糖果每个孩子至少分配k个糖果k1 这些问题需要调整算法策略9. 实际应用场景虽然这个问题看起来是抽象的算法题但它实际上模拟了许多现实世界的资源分配场景员工奖金分配根据绩效评分分配奖金避免相邻员工间的不公平感网络带宽分配根据节点优先级分配带宽满足相邻节点间的约束任务调度优先级确保高优先级任务获得更多资源同时满足局部约束理解这类问题的解法有助于我们在实际工作中处理类似的约束优化问题。10. 个人实现心得在实际编码实现这个算法时有几个关键点值得注意初始化时给所有孩子分配1个糖果是必须的这保证了最基本的约束条件从右到左遍历时必须使用max操作来保留之前满足的左约束结果处理边界条件时要小心特别是第一个和最后一个孩子只需要考虑单侧约束我发现画图帮助很大。对于测试用例[1,3,4,5,2]可以这样可视化评分[1, 3, 4, 5, 2] 左遍历[1, 2, 3, 4, 1] 右遍历[1, 1, 1, 2, 1] 最终取max[1, 2, 3, 4, 1] → 总和11另一个技巧是先用小测试用例手动计算预期结果再与程序输出对比这样可以快速定位问题。