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

1. 问题背景与核心挑战

LeetCode 135题"分发糖果"是一个经典的贪心算法应用题，它模拟了现实中的资源分配场景。题目描述为：N个孩子站成一排，每个孩子有一个评分值。你需要按照以下要求给这些孩子分发糖果：

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

这个看似简单的问题背后隐藏着两个关键约束条件：

1. 左约束：当前孩子如果比左边孩子评分高，则糖果数必须多于左边
2. 右约束：当前孩子如果比右边孩子评分高，则糖果数必须多于右边

这两个约束条件形成了典型的"双向约束"问题，也是这个题目的核心难点所在。我们需要找到一个同时满足这两个约束条件的糖果分配方案，并且使总糖果数最小。

2. 贪心算法解题思路解析

2.1 贪心算法的适用性分析

贪心算法特别适合这类具有局部最优性质的问题。在这个题目中，每个孩子的糖果分配只需要考虑其与直接相邻孩子的关系，不需要考虑更远的孩子。这种局部性质使得我们可以分步骤、分阶段地解决问题。

贪心选择性质体现在：为了满足总糖果数最小，每个孩子应该尽可能被分配最少的糖果（即在满足约束条件下取最小值）。这种局部最优的选择最终会导致全局最优解。

2.2 双向处理策略

解决这个问题的关键在于如何处理双向约束。一个有效的策略是将问题分解为两个单向处理：

1. 从左到右遍历：只考虑每个孩子与其左边孩子的关系
2. 从右到左遍历：只考虑每个孩子与其右边孩子的关系

然后，对于每个孩子，取两次遍历结果中的较大值作为最终分配的糖果数。这样可以确保同时满足两个方向的约束。

3. 详细实现步骤

3.1 初始化阶段

首先，我们初始化一个长度为n的数组candy，其中n是孩子的数量。初始时，每个孩子至少分配1个糖果：

n = len(ratings) candy = [1] * n

3.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[i+1]: candy[i] = max(candy[i], candy[i+1] + 1)

这个遍历保证了对于任意i，如果ratings[i] > ratings[i+1]，那么candy[i] > candy[i+1]。

3.4 计算总糖果数

最后，我们只需要将所有分配的糖果数相加即可：

total = sum(candy)

4. 算法正确性证明

4.1 约束满足性

通过两次遍历，我们确保了：

1. 从左到右遍历后，所有左约束被满足
2. 从右到左遍历后，所有右约束被满足（因为取max操作不会破坏已经满足的左约束）

因此，最终的分配方案同时满足两个方向的约束。

4.2 最小性证明

要证明这个方案使用的总糖果数是最小的，可以考虑：

1. 每个孩子最终分配的糖果数是满足其左右约束所需的最小值
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[i+1]+1，会破坏已经建立的左约束。例如：

对于[1,2,3,1]：

• 从左到右后：[1,2,3,1]
• 如果从右到左不加max：[1,2,2,1] → 第二个3会被错误地减少
• 正确做法保持3不变

7.3 调试技巧

当遇到错误时，可以：

1. 打印每次遍历后的糖果分配数组
2. 检查每个位置的分配是否满足其与相邻位置的约束
3. 特别注意评分相等的情况，确保没有不必要的增加

8. 算法优化与变种思考

8.1 空间优化

如果允许修改输入数组，我们可以利用输入数组的一部分空间来存储中间结果，将空间复杂度降低到O(1)。但在实际面试中，通常不需要这样做，清晰比微优化更重要。

8.2 变种问题：环形排列

如果孩子们是围成一个圈（即第一个和最后一个也相邻），问题会变得更加复杂。这种情况下，我们需要：

1. 找到评分最小的孩子，从那里开始分配
2. 或者将环形问题转换为线性问题处理

8.3 变种问题：不同约束条件

如果约束条件变化，比如：

• 评分相等的孩子必须得到相同数量的糖果
• 每个孩子至少分配k个糖果（k>1） 这些问题需要调整算法策略

9. 实际应用场景

虽然这个问题看起来是抽象的算法题，但它实际上模拟了许多现实世界的资源分配场景：

1. 员工奖金分配：根据绩效评分分配奖金，避免相邻员工间的不公平感
2. 网络带宽分配：根据节点优先级分配带宽，满足相邻节点间的约束
3. 任务调度优先级：确保高优先级任务获得更多资源，同时满足局部约束

理解这类问题的解法有助于我们在实际工作中处理类似的约束优化问题。

10. 个人实现心得

在实际编码实现这个算法时，有几个关键点值得注意：

1. 初始化时给所有孩子分配1个糖果是必须的，这保证了最基本的约束条件
2. 从右到左遍历时，必须使用max操作来保留之前满足的左约束结果
3. 处理边界条件时要小心，特别是第一个和最后一个孩子只需要考虑单侧约束

我发现画图帮助很大。对于测试用例[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

另一个技巧是先用小测试用例手动计算预期结果，再与程序输出对比，这样可以快速定位问题。