LeetCode: 分发糖果问题详解

在 LeetCode 的众多题目中，“分发糖果”（Candy） 是一道既具有一定挑战性，又能很好地考察算法思维和编程能力的题目。本题主要围绕如何根据孩子们的评分合理地分发糖果，以满足每个孩子至少得到一颗糖果，并且相邻孩子中评分高的孩子得到更多糖果的条件。通过解决这道题，我们不仅可以锻炼算法设计的能力，还能深入理解贪心算法在实际问题中的应用。

目录#

  1. 问题描述
  2. 问题分析
  3. 解决方案
    • 两次遍历解法
    • 优化的一次遍历解法
  4. 复杂度分析
  5. 代码实现
  6. 总结
  7. 参考资料

1. 问题描述#

题目链接：LeetCode 135. 分发糖果

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

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

那么这样下来，老师至少需要准备多少颗糖果呢？

示例#

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

2. 问题分析#

本题的核心在于如何根据孩子的评分来合理地分配糖果，同时要满足相邻孩子中评分高的孩子得到更多糖果的条件。我们可以将问题拆分成两个部分来考虑：

  • 从左到右遍历数组，保证每个孩子和其左边孩子满足条件。
  • 从右到左遍历数组，保证每个孩子和其右边孩子满足条件。

通过这两次遍历，我们可以确保每个孩子都能满足相邻孩子之间的糖果分配规则。

3. 解决方案#

3.1 两次遍历解法#

这种解法的基本思路是先从左到右遍历数组，给每个孩子分配一个初始的糖果数，使得每个孩子和其左边孩子满足条件。然后再从右到左遍历数组，调整每个孩子的糖果数，使得每个孩子和其右边孩子也满足条件。

具体步骤如下：

  1. 初始化一个长度为 n 的数组 candy，其中 n 是孩子的数量，每个元素初始值为 1，表示每个孩子至少有一颗糖果。
  2. 从左到右遍历数组 ratings，如果当前孩子的评分比前一个孩子高，则当前孩子的糖果数比前一个孩子多 1。
  3. 从右到左遍历数组 ratings，如果当前孩子的评分比后一个孩子高，并且当前孩子的糖果数不大于后一个孩子的糖果数，则当前孩子的糖果数为后一个孩子的糖果数加 1。
  4. 最后，将数组 candy 中的所有元素相加，得到总共需要的糖果数。

3.2 优化的一次遍历解法#

一次遍历解法的核心思想是利用动态调整的方法，在一次遍历中完成糖果的分配。我们需要记录当前上升和下降序列的长度，根据这些信息来合理地分配糖果。

具体步骤如下：

  1. 初始化变量 candy 为 1，表示第一个孩子至少有一颗糖果，up 表示上升序列的长度，down 表示下降序列的长度，peak 表示上升序列的峰值。
  2. 从第二个孩子开始遍历数组 ratings，根据当前孩子的评分与前一个孩子的评分比较结果，更新 up、down 和 peak 的值。
  3. 如果当前孩子的评分比前一个孩子高，说明处于上升序列，up 加 1，down 重置为 0，peak 更新为 up，并将 candy 加上 up。
  4. 如果当前孩子的评分比前一个孩子低，说明处于下降序列，down 加 1，up 重置为 0，根据 down 和 peak 的大小关系调整 candy。
  5. 如果当前孩子的评分与前一个孩子相同，up 和 down 都重置为 0，peak 也重置为 0，candy 加 1。

4. 复杂度分析#

两次遍历解法#

  • 时间复杂度：O(n)O(n)，其中 nn 是孩子的数量。需要遍历数组两次。
  • 空间复杂度：O(n)O(n)，需要额外的数组 candy 来记录每个孩子的糖果数。

优化的一次遍历解法#

  • 时间复杂度：O(n)O(n)，只需要遍历数组一次。
  • 空间复杂度：O(1)O(1)，只需要常数级的额外空间。

5. 代码实现#

两次遍历解法（Python）#

def candy(ratings):
    n = len(ratings)
    candy = [1] * n
 
    # 从左到右遍历
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candy[i] = candy[i - 1] + 1
 
    # 从右到左遍历
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1] and candy[i] <= candy[i + 1]:
            candy[i] = candy[i + 1] + 1
 
    return sum(candy)

优化的一次遍历解法（Python）#

def candy(ratings):
    n = len(ratings)
    if n <= 1:
        return n
    candy = 1
    up = 0
    down = 0
    peak = 0
 
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            up += 1
            down = 0
            peak = up
            candy += up + 1
        elif ratings[i] < ratings[i - 1]:
            up = 0
            down += 1
            if down <= peak:
                candy += down
            else:
                candy += down + 1
        else:
            up = 0
            down = 0
            peak = 0
            candy += 1
 
    return candy

调用示例#

ratings = [1, 0, 2]
print(candy(ratings))  # 输出: 5

6. 总结#

通过解决“分发糖果”这道题，我们学习了两种不同的解法：两次遍历解法和优化的一次遍历解法。两次遍历解法思路清晰，容易理解，但需要额外的 O(n)O(n) 空间；优化的一次遍历解法虽然实现起来相对复杂一些，但只需要常数级的额外空间，时间复杂度也为 O(n)O(n)。在实际应用中，我们可以根据具体情况选择合适的解法。

7. 参考资料#

希望这篇文章能帮助你更好地理解和解决“分发糖果”这道题。如果你有任何疑问或建议，欢迎在评论区留言。

2026-06