分发糖果

周子力大约 8 分钟教学文档贪心法

题目描述

解题思路

好的，这是一个经典的贪心算法问题。它的核心在于处理"相邻"关系，既要满足左边邻居的约束，又要满足右边邻居的约束。

求解思路：

理解题意：
- 每个孩子至少有 1 颗糖果。
- 如果一个孩子的评分比他左边的邻居高，那么他的糖果必须比左边邻居多。
- 如果一个孩子的评分比他右边的邻居高，那么他的糖果必须比右边邻居多。
- 我们的目标是最小化总糖果数。
贪心策略：
- 这个问题不能简单地一次遍历就解决，因为一个孩子的糖果数同时受到左右两边邻居的约束。一个孩子左边的评分变化会影响他右边孩子的糖果数，反之亦然。
- 一个有效的策略是分两步走：
  - 第一步（从左到右）：只考虑“右边孩子比左边孩子评分高”的情况。遍历数组，如果 ratings[i] > ratings[i-1]，那么 candies[i] 必须比 candies[i-1] 多。我们让 candies[i] = candies[i-1] + 1。这样可以保证所有“右边比左边高”的约束都得到满足。这一步从左到右进行，确保了每个孩子都满足了相对于其左邻居的约束。
  - 第二步（从右到左）：只考虑“左边孩子比右边孩子评分高”的情况。遍历数组，如果 ratings[i] > ratings[i+1]，那么 candies[i] 必须比 candies[i+1] 多。此时，candies[i] 的值应该是它当前值和 candies[i+1] + 1 中的最大值，即 candies[i] = max(candies[i], candies[i+1] + 1)。这样做是为了在不破坏第一步结果的前提下，满足相对于其右邻居的约束。取最大值可以确保 candies[i] 既满足了左邻居的约束（通过第一步），又满足了右邻居的约束。
- 通过这两步，我们确保了所有相邻关系的约束都得到了满足，同时糖果数也是最少的。

Python 代码实现：

def candy(ratings):
    """
    :param ratings: List[int] - 每个孩子的评分
    :return: int - 需要准备的最少糖果数目
    """
    n = len(ratings)
    if n == 0:
        return 0
    if n == 1:
        return 1

    # 初始化糖果数组，每个孩子至少有1颗糖果
    candies = [1] * n

    # --- 第一步：从左到右遍历，处理 "ratings[i] > ratings[i-1]" 的情况 ---
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            # 如果当前孩子评分比左边高，则糖果数至少比左边多1
            candies[i] = candies[i - 1] + 1
    # print(f"左到右遍历后: {candies}") # 可用于调试

    # --- 第二步：从右到左遍历，处理 "ratings[i] > ratings[i+1]" 的情况 ---
    # 从倒数第二个孩子开始，因为最后一个孩子没有右边邻居
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            # 如果当前孩子评分比右边高，则糖果数必须比右边多
            # 但同时要保证不破坏第一步的结果，所以取最大值
            candies[i] = max(candies[i], candies[i + 1] + 1)
    # print(f"右到左遍历后: {candies}") # 可用于调试

    # 计算总糖果数
    return sum(candies)

# --- 示例测试 ---
# 示例 1
ratings1 = [1, 0, 2]
print(f"输入: ratings = {ratings1}")
print(f"输出: {candy(ratings1)}")  # 输出: 5
# 解释: 糖果分配 [2, 1, 2] -> 2+1+2=5

# 示例 2
ratings2 = [1, 2, 2]
print(f"输入: ratings = {ratings2}")
print(f"输出: {candy(ratings2)}")  # 输出: 4
# 解释: 糖果分配 [1, 2, 1] -> 1+2+1=4

# 示例 3: 平稳序列
ratings3 = [7, 8, 8, 8, 9, 10]
print(f"输入: ratings = {ratings3}")
print(f"输出: {candy(ratings3)}")  # 输出: 9
# 解释: 糖果分配 [1, 2, 1, 1, 2, 3] -> 1+2+1+1+2+3=10
# 注意：中间三个8的评分，因为与邻居相等，所以可以只给1颗糖果。
# 但左边的8(索引1)比7(索引0)高，所以是2。右边的8(索引4)比9(索引5)低，所以是2。
# 再次检查：ratings=[7, 8, 8, 8, 9, 10], candies=[1, 2, 1, 1, 2, 3]
# i=0: 1 candy, ratings 7 vs 8 (right) -> ok
# i=1: 2 candies, ratings 8 > 7 (left), 8 vs 8 (right) -> ok
# i=2: 1 candy, ratings 8 vs 8 (left), 8 vs 8 (right) -> ok
# i=3: 1 candy, ratings 8 vs 8 (left), 8 < 9 (right) -> ok
# i=4: 2 candies, ratings 9 > 8 (left), 9 < 10 (right) -> ok
# i=5: 3 candies, ratings 10 > 9 (left) -> ok
# 总数 1+2+1+1+2+3 = 10。抱歉，上面计算有误，应为10。
print(f"修正解释: 糖果分配 [1, 2, 1, 1, 2, 3] -> 1+2+1+1+2+3={sum([1, 2, 1, 1, 2, 3])}")
# 实际输出是10，不是9。代码是正确的。示例3的输出是10。

代码解释：

candies = [1] * n：初始化一个长度为 n 的数组 candies，每个元素都为 1，确保每个孩子至少有 1 颗糖果。
第一次遍历 (for i in range(1, n))：从左到右，检查 ratings[i] > ratings[i-1]。如果成立，candies[i] 就更新为 candies[i-1] + 1。这一步确保了所有“右边比左边高”的评分关系在糖果数上得到了体现。
第二次遍历 (for i in range(n - 2, -1, -1))：从右到左，检查 ratings[i] > ratings[i+1]。如果成立，candies[i] 就更新为 max(candies[i], candies[i+1] + 1)。max 函数确保了更新后的糖果数既满足当前的右邻居约束，又不会低于第一步中已经满足的左邻居约束。
return sum(candies)：最后返回数组 candies 的总和，即为所需最少糖果数。

分发糖果问题：注意事项与启发

1. 理解约束的双向性

核心难点：该问题的关键在于约束是双向的。“评分更高的孩子获得更多糖果”这一规则，意味着一个孩子的糖果数同时受到其左边邻居和右边邻居的评分影响。例如，对于序列 [1, 3, 2]，中间的孩子 3 不仅要多于左边的 1，也要多于右边的 2。如果只考虑单向（比如只看左边），很容易遗漏约束。
启发：遇到需要同时满足多个方向或条件的问题时，可以考虑将其分解为几个独立的子问题来解决。

2. 分解策略：两次遍历

策略核心：将复杂的双向约束分解为两个简单的单向约束。
- 左到右遍历：处理“如果 ratings[i] > ratings[i-1]，则 candies[i] > candies[i-1]”的约束。
- 右到左遍历：处理“如果 ratings[i] > ratings[i+1]，则 candies[i] > candies[i+1]”的约束。
注意：第二次遍历必须使用 max 函数。例如，在序列 [1, 3, 2, 1] 中，左到右遍历后 candies 可能为 [1, 2, 1, 1]。当右到左遍历到索引 1 的孩子时，其 ratings[1] > ratings[2]（3 > 2），需要满足 candies[1] > candies[2]。candies[2] 此时是 1，所以 candies[1] 需要变成 candies[2] + 1 = 2。但我们不能直接赋值 candies[1] = 2，因为 candies[1] 已经是 2 了（满足了左邻居的约束）。如果直接赋值，可能会破坏第一次遍历的结果。因此，使用 candies[1] = max(candies[1], candies[2] + 1)，取两者中的较大值，这样既能满足右邻居的约束，又不会破坏左邻居的约束。

3. 贪心思想的体现

局部最优：在每次比较中，我们只给需要多一颗糖果的孩子最少的增量（即多 1 颗）。例如，如果一个孩子比邻居高 100 分，我们也不会给他多 100 颗糖，而是只多 1 颗。这体现了贪心算法“局部最优”的思想。
全局最优：通过两次遍历，每次都只进行最小的调整，最终得到的结果是满足所有约束条件下的最小糖果总数。这证明了这种贪心策略是正确的。

4. 边界条件处理

注意：在遍历时要特别小心边界。
- 左到右遍历：从索引 1 开始，因为索引 0 没有左邻居。
- 右到左遍历：从索引 n-2 结束，因为索引 n-1 没有右邻居。
- 空数组/单元素：虽然题目通常会保证输入有效，但代码应能处理 n=0 或 n=1 的情况，这通常需要在开头进行特判。

5. 数据初始化

注意：candies 数组必须初始化为 [1] * n，而不是 [0] * n。因为题目明确要求“每个孩子至少分配到 1 个糖果”。这是所有后续操作的基础。

6. 启发

处理复杂约束：当一个问题的约束条件相互交织、难以一次性解决时，可以尝试将其分解为几个独立或更容易处理的子问题。分发糖果问题就是将双向约束分解为两个单向约束的经典案例。
两次遍历的模式：这是一种非常重要的编程模式，尤其适用于需要考虑左右（或前后）两个方向影响的场景。例如，求一个数组中每个元素左边所有元素的乘积，再乘以右边所有元素的乘积（类似问题），或者本题。
贪心与动态规划：这个问题也可以用动态规划的思路来思考，但贪心解法更为直接和高效。理解贪心策略的正确性（即为什么这种局部最优能导致全局最优）是关键。在本题中，因为糖果数只与相邻的、评分更低的邻居有关，所以局部的最小调整不会影响全局的最优性。
代码的可读性：在编写代码时，可以通过注释来清晰地表明“第一次遍历做什么”、“第二次遍历做什么”，这样代码的逻辑会更加清晰。