分发糖果问题如何用贪心求最少糖果数？（LeetCode 135）

简化版

n 个孩子站成一排，各有评分 ratings[i]。分糖果要满足：每人至少 1 颗；相邻两人中评分更高的必须拿更多糖。求满足条件的最少糖果总数。贪心策略：做两趟遍历——先从左往右，若 ratings[i] > ratings[i-1] 则 candy[i] = candy[i-1] + 1；再从右往左，若 ratings[i] > ratings[i+1] 则 candy[i] = max(candy[i], candy[i+1] + 1)。两个方向分别满足「比左邻高」和「比右邻高」的约束，取 max 同时满足，最后求和。

详细版

int candy(int[] ratings) {
    int n = ratings.length;
    int[] candy = new int[n];
    Arrays.fill(candy, 1);                 // 每人至少 1 颗
    // 第一趟：从左到右，保证「比左邻评分高的人糖更多」
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candy[i] = candy[i - 1] + 1;
        }
    }
    // 第二趟：从右到左，保证「比右邻评分高的人糖更多」
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candy[i] = Math.max(candy[i], candy[i + 1] + 1);
        }
    }
    int sum = 0;
    for (int c : candy) sum += c;
    return sum;
}

两个方向拆解约束：一个相邻约束其实是两条——「比左边高要更多」和「比右边高要更多」。分两趟各管一个方向。
第二趟取 max：从右到左时不能直接覆盖，要用 max 保留第一趟已满足的左侧约束。
复杂度：O(n) 时间、O(n) 空间。

完整版教学

一、难点：一个约束其实是两个方向

约束「相邻中评分高的糖更多」看似一条，实则对每个孩子 i 同时施加了两个要求：

若 ratings[i] > ratings[i-1]（比左邻高）→ candy[i] > candy[i-1]；
若 ratings[i] > ratings[i+1]（比右邻高）→ candy[i] > candy[i+1]。

难点在于这两个要求耦合在一起：你调整 i 的糖，会牵连左右。如果试图一趟遍历同时满足，会顾此失彼。贪心的巧思是解耦——分两趟，每趟只管一个方向，最后合并。

二、第一趟：从左到右，管好「左邻」

初始每人 1 颗。从左往右扫，只处理「比左边高」的情况：ratings[i] > ratings[i-1] 时，candy[i] = candy[i-1] + 1。

这一趟保证了：所有「评分比左邻高」的孩子，糖都比左邻多。像 1 2 3 这种连续上升，会得到 1 2 3。但它没管右边——比如 3 2 1，从左到右扫全是下降，结果是 1 1 1，右邻约束还没满足。

三、第二趟：从右到左，管好「右邻」，且不破坏第一趟

从右往左扫，处理「比右邻高」：ratings[i] > ratings[i+1] 时，i 应该比右邻糖多，即至少 candy[i+1] + 1。

关键是 max：candy[i] = max(candy[i], candy[i+1] + 1)。为什么不能直接赋值？因为第一趟可能已经给了 candy[i] 一个较大值来满足左邻约束，第二趟若直接覆盖会破坏它。用 max 取两个方向要求的较大者，就能同时满足左、右两个约束——既 ≥ 左邻要求，又 ≥ 右邻要求。

举例 1 3 2 1（评分）：

第一趟（左→右）：1 2 1 1（只有 3>1 那步 +1）。
第二趟（右→左）：i=2（评分2>1）→ max(1, 1+1)=2；i=1（评分3>2）→ max(2, 2+1)=3；i=0（评分1<3）不变。结果 1 3 2 1，总和 7。✔ 每个高分都比两边邻居糖多。

四、贪心为什么给出最小值

每一步我们都只在必须 +1 时才 +1，且加的是「刚好比邻居多 1」的最小增量，从不多给。两趟取 max 保证「同时满足两个方向的最紧下界」，而这个下界对每个孩子都是不可再降的（再少就违反约束）。既然每个人都取到了各自约束允许的最小糖数，总和自然最小。

五、常见错误与进阶

错误 1：只做一趟遍历。无论从哪个方向单趟，都只能满足一侧邻居，另一侧会漏。必须两趟。
错误 2：第二趟用赋值而非 max。会覆盖掉第一趟的成果，导致左邻约束被破坏。
错误 3：评分相等的处理。题目只要求「更高的更多」，评分相等的相邻两人没有大小约束，各自可以是 1（或由各自另一侧决定），不要给相等的也 +1。
进阶：O(1) 空间的一趟解法。可以用「统计连续上升坡长 up、连续下降坡长 down」的方式一趟算出，但两趟数组法更直观易记，面试首选。

六、贪心选择为什么不会堵死未来

本题每一步选择是：左到右给满足左邻约束的最小值，再右到左用 max 保留左约束并补足右约束。

正确性不能只靠直觉，核心证明是：每一趟分别计算一个方向必须达到的下界，最终取两方向下界最大值是同时可行的逐点最小分配。这说明任意最优方案都能调整为包含当前贪心选择的方案，且目标值不会变差。

排序或预处理，建立可比较的选择顺序
维护“当前选择给未来留下的有效边界”
若候选不劣于现有边界，则提交选择并更新状态

数字推演：ratings=[1,0,2] 左扫 [1,1,2]，右扫合并为 [2,1,2]，总数 5。

记忆钩子：贪心不是“选眼前最大”，而是选一个能被交换论证证明、对未来最宽松的代表。

七、退化边界、复杂度与反例检查

实现边界是：第二趟不能直接覆盖第一趟；相等评分没有严格多糖要求；答案总和可能比 n 大很多。

检查项	必须回答
排序键	为什么按这个维度和方向排序
局部选择	它保留了什么未来可能性
正确性	交换、领先或反证中的哪一种
失败边界	哪个题目条件一改就不能贪心
复杂度	排序成本与扫描成本是否都计入

测试时至少覆盖单元素、全部相等、严格递增/递减、恰好卡在边界、局部最优容易误导的反例。若无法写出交换论证或领先性质，应暂停使用贪心，转而尝试动态规划、搜索或数据结构。

八、常见误区与追问

误区：一趟从左到右足够。 无法处理右邻评分更低的约束。
误区：第二趟直接写 right+1。 会破坏第一趟已满足的左约束，应取 max。
误区：评分相等糖果也必须相等。 题目只约束评分严格更高的邻居。
追问：为什么结果最小？ 每个位置恰取两个必要下界的最大值。
追问：能否 O(1) 空间？ 可用山峰/坡度计数优化，但实现更易错。
追问：全递减数组结果是多少？ 糖果为 n,n-1,…,1，总数 n(n+1)/2。

九、加强记忆

分发糖果 = 两趟遍历拆解双向约束：相邻约束对每人其实是「比左邻高要更多」+「比右邻高要更多」两条。第一趟左→右：ratings[i]>ratings[i-1] 则 candy[i]=candy[i-1]+1（管左邻）；第二趟右→左：ratings[i]>ratings[i+1] 则 candy[i]=max(candy[i], candy[i+1]+1)（管右邻，必须 max 否则毁掉第一趟）。每步只加最小增量，故总和最少。初始全 1，评分相等无约束。O(n) 时间 O(n) 空间。

简化版

详细版