LeetCode 135. 分发糖果

约 5 分钟
文章信息 17 个分类 2 个标签
分类
LeetCode CodeTop 困难 未解决 20-50 面试经典 150 题 腾讯 字节 阿里 华为 微软 拼多多 京东 小米 网易 快手 虾皮
标签
数组 贪心

题目描述

✅ 135. 分发糖果

image-20260928203845415

image-20260928203845416

题意分析

给一排孩子分配糖果，每人至少一颗。若某个孩子的评分高于紧邻的孩子，他的糖果数也必须更多；只比较相邻位置，不要求评分更高的人比所有低分孩子都拿得多。

相邻评分相等时没有糖果数量的大小关系限制。要求满足所有这些条件，并使总糖果数最少，不能只找到一种可行分配。

解法：左右两次扫描取最大约束

核心思路

[!blue]

一个孩子可能同时受到左右两边的限制。先分别求出只考虑左邻居、只考虑右邻居时的最低需求，再取足以满足两边的较大值，就能把相互牵连的要求拆开。

从左到右扫描时，左邻居的需求已经确定。若当前评分更高，当前至少要比左边多一颗，令 candies[i] = candies[i - 1] + 1；否则左侧没有额外要求，保留最初的一颗。这给出了每个位置由连续上升段产生的必要下界。

再从右到左处理右侧限制。若当前评分高于右邻居，它至少需要 candies[i + 1] + 1 颗；但第一次扫描已有的左侧下界不能丢，因此取原值与这个需求的最大值。右邻居已在本趟处理完，下降段的要求便能逐个向左传递。

为什么这样已经最少？任何合法方案都不能低于任一方向算出的下界，而取较大值没有额外增加不需要的糖果。它也确实可行：上升相邻对由左扫保证，下降相邻对由右扫保证；右扫只会为“左边评分更高”的相邻对增加左边的糖果，不会破坏该对要求，若再影响更左边，则下一轮会继续补足。

因此两次扫描结束后，每个位置都达到同时满足左右约束的最低值，求和就是最少总数。

解题步骤

  1. 建立与评分数组等长的 candies，全部初始化为 1，满足每人至少一颗。
  2. 从第二个孩子向右扫描，当前评分高于左邻居时，把当前糖果数设为左邻居加一。
  3. 从倒数第二个孩子向左扫描，当前评分高于右邻居时，取当前糖果数与右邻居加一中的较大值。
  4. 相等评分不触发任何一侧的增加，最后累加全部糖果数并返回。

代码实现

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];

        Arrays.fill(candies, 1);

        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                // 同时满足左侧扫描和右侧扫描给出的最小约束。
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        int ans = 0;

        for (int candy : candies) {
            ans += candy;
        }

        return ans;
    }
}

func candy(ratings []int) int {
    n := len(ratings)
    candies := make([]int, n)
    for i := 0; i < n; i++ {
        candies[i] = 1
    }

    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            candies[i] = candies[i-1] + 1
        }
    }
    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] {
            needed := candies[i+1] + 1
            // 保留左侧约束与右侧约束中的较大者，不能覆盖已经满足的要求。
            if candies[i] < needed {
                candies[i] = needed
            }
        }
    }

    ans := 0
    for _, candy := range candies {
        ans += candy
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$，两次扫描和一次求和都为线性时间。
  • 空间复杂度：$O(n)$，使用一个与评分数组等长的糖果数组。

关键点总结

[!green]

  • 两遍扫描分别传播左侧和右侧的必要下界，方向必须与依赖方向一致。
  • 第二遍用最大值合并要求，既补足右侧约束，也保留左侧已经确定的下界。
  • 严格更高的评分才要求严格更多糖果，相等评分不建立递增关系。

易错点总结

[!yellow]

  • 只从左向右扫，会遗漏下降段中左边孩子必须比右边多的要求。
  • 右扫直接覆盖原值，可能把由较长上升段决定的峰值降低，破坏左侧约束。
  • 第二遍也从左向右走，右邻居尚未计算完整，无法一次正确传播连续下降段的需求。
  • 默认糖果数为 0，会违反每人至少一颗的基本条件。
  • 用 >= 触发递增，会给相等评分的孩子增加不必要的糖果，导致结果不再最小。

相似题目

题目 难度 关联与区别
42. 接雨水 困难 同样结合左右两侧约束，本题取两侧糖果最低要求的较大值，接雨水取两侧边界水位的较小值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/28450664
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！