贪心算法解决LeetCode糖果分配问题详解

1. 问题背景与核心挑战

LeetCode 135题"分发糖果"是一个经典的贪心算法应用题，它模拟了实际生活中按规则分配有限资源的情境。题目要求在一排孩子中根据他们的评分来分配糖果，同时满足两个基本约束条件：

1. 每个孩子至少分配到1个糖果
2. 评分更高的孩子必须比相邻孩子获得更多的糖果

这个看似简单的问题背后隐藏着典型的双向约束难题。我最初尝试时，以为只需要简单地遍历一次就能解决，结果发现需要考虑左右两侧的相邻关系，这让我意识到需要更系统的解法。

2. 贪心算法的选择依据

为什么这个问题适合用贪心算法？关键在于问题具有"无后效性"和"最优子结构"这两个贪心算法的适用特征：

• 无后效性：当前孩子的糖果分配只与相邻孩子的分配有关
• 最优子结构：全局最优解可以通过局部最优解组合得到

在实际编码中，我采用了两次独立遍历的策略：

1. 从左到右遍历，处理右邻居约束
2. 从右到左遍历，处理左邻居约束

这种分而治之的思想是解决双向约束问题的常见模式，在动态规划问题中也经常出现。

3. 详细实现步骤解析

3.1 初始化与第一次遍历

def candy(ratings): n = len(ratings) candies = [1] * n # 初始每人至少1个糖果 # 从左到右遍历，处理右邻居约束 for i in range(1, n): if ratings[i] > ratings[i-1]: candies[i] = candies[i-1] + 1

这个阶段确保当右边孩子评分更高时，其糖果数比左边多1。注意我们初始化为每人1个糖果，这是满足第一个约束条件的基础。

3.2 第二次反向遍历

# 从右到左遍历，处理左邻居约束 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)

第二次遍历需要特别注意：不能简单地赋值，而要取max值。这是因为要同时满足两次遍历的结果。我最初在这里犯错，导致某些测试用例失败。

4. 复杂度分析与优化空间

时间复杂度：O(n)，因为我们只进行了两次线性遍历 空间复杂度：O(n)，用于存储糖果分配数组

虽然这个解法已经是最优的，但在实际面试中，面试官可能会问：

"能否用O(1)空间复杂度解决？"

经过思考，我认为理论上不可能，因为我们需要记住之前的分配结果。不过可以尝试用数学方法计算斜率变化点，但这会大大增加实现复杂度。

5. 常见错误与调试技巧

在实现过程中，我遇到了几个典型错误：

1. 忘记初始化糖果数组为1

   • 症状：最小糖果数计算错误
   • 修复：确保初始化为[1] * n

2. 第二次遍历时直接赋值而非取max

   • 症状：[1,3,4,5,2]这样的用例会失败
   • 修复：使用max保留两次遍历的结果

3. 边界条件处理不当

   • 症状：空数组或单元素数组返回错误
   • 修复：添加特殊条件判断

调试时可以先用小测试用例，如：

• [1,0,2] 应该返回5
• [1,2,2] 应该返回4

6. 实际应用场景延伸

这个问题看似简单，但其核心思想在多个领域有实际应用：

1. 资源分配系统：在带宽分配、CPU时间片分配等场景
2. 交通信号灯时序设计：考虑相邻路口的约束
3. 生产流水线平衡：确保各工位负荷合理分布

理解这类双向约束问题的解法，可以帮助我们在更复杂的系统设计中建立正确的约束处理模型。

7. 算法变种与进阶思考

如果题目条件变化，我们的解法也需要相应调整：

1. 如果相邻相同评分的孩子要求糖果数相同？

   • 需要增加平局条件的处理

2. 如果糖果数有上限限制？

   • 需要在遍历时增加上限检查

3. 如果要求环形排列（首尾也视为相邻）？

   • 需要额外处理首尾关系

这些变种在各大公司的面试题中都曾出现过，理解基础解法后，可以尝试自己实现这些变种。

8. 编码风格与面试技巧

在面试中实现这个问题时，建议：

1. 先明确叙述算法思路
2. 处理边界条件要仔细
3. 变量命名要有意义（如用candies而非res）
4. 可以画图说明两次遍历的过程
5. 主动讨论时间/空间复杂度

我在面试候选人时，发现很多人能写出代码，但无法解释为什么这样做是正确的。能够清晰论证算法正确性往往比单纯写出代码更重要。

9. 测试用例设计指南

全面的测试用例应该包括：

1. 基础用例：[1,0,2] → 5
2. 平局情况：[1,2,2] → 4
3. 单峰序列：[1,3,2,1] → 7
4. 单调递增：[1,2,3,4] → 10
5. 单调递减：[4,3,2,1] → 10
6. 全等序列：[2,2,2] → 3
7. 空数组：[] → 0
8. 单元素数组：[5] → 1

养成先写测试用例的习惯可以大大减少调试时间。

10. 不同语言实现要点

虽然算法逻辑相同，但不同语言实现时有细微差别：

C++实现注意：

• 使用vector而非原生数组
• 注意索引从0开始

Java实现注意：

• 数组初始化语法
• 可以使用Arrays.fill初始化

JavaScript实现注意：

• 数组的map和reduce方法可以简化代码
• 但两次遍历的逻辑仍然需要

无论哪种语言，核心算法逻辑保持一致，只是语法细节需要调整。