❌ LeetCode 135 - 分发糖果（Candy）

问题描述

想象一下，你是一位老师，要给班上的孩子们分发糖果 🍭。孩子们排成一排，每个孩子都有一个评分（可以理解为考试成绩）。

分糖果的规则很简单：

每个孩子至少要有 1 颗糖果（不能让任何孩子空手而归）
如果相邻的两个孩子，评分高的那个必须比评分低的拿到更多糖果

你的任务： 用最少的糖果数量，让所有孩子都满意！

举个例子：

1 2	孩子评分：[1, 0, 2] 最优分配：[2, 1, 2] 总共需要 5 颗糖果

为什么这样分配？

第1个孩子(评分1) vs 第2个孩子(评分0)：1 > 0，所以第1个孩子要比第2个多 → 2颗 vs 1颗 ✅
第2个孩子(评分0) vs 第3个孩子(评分2)：0 < 2，所以第3个孩子要比第2个多 → 1颗 vs 2颗 ✅

我最开始的错误想法 😅

❌ 想法一：只看左边邻居

我刚开始想，既然要满足规则，那就从左到右遍历，每次只要比左边邻居满足条件就行了：

// ❌ 这样想是错的！
func candy(ratings []int) int {
    n := len(ratings)
    candies := make([]int, n)
    candies[0] = 1  // 第一个孩子给1颗
    
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            candies[i] = candies[i-1] + 1  // 比左边多1颗
        } else {
            candies[i] = 1  // 否则就给1颗
        }
    }
    // 计算总数...
}

这样做错在哪里？

让我们用例子 [1,0,2] 试试：

第1个孩子：给1颗
第2个孩子：评分0 < 评分1，所以给1颗
第3个孩子：评分2 > 评分0，所以给2颗

结果：[1,1,2]

问题出现了！ 第1个孩子评分1，第2个孩子评分0，但是他们都拿1颗糖果！这违反了规则：评分高的应该拿更多糖果。

教训：只看一边是不够的，我们需要同时满足左右两边的关系！

❌ 想法二：边遍历边修正

然后我想，那我在遍历的时候，发现问题就立即修正：

// ❌ 这样也是错的！
for i := 1; i < n; i++ {
    if ratings[i] > ratings[i-1] {
        candies[i] = candies[i-1] + 1
    } else {
        candies[i] = 1
        // 发现左边的孩子糖果可能不够，马上修正
        if ratings[i-1] > ratings[i] && candies[i-1] <= candies[i] {
            candies[i-1] = candies[i] + 1
        }
    }
}

这样还是错的！ 因为当我修改前面孩子的糖果数时，可能又影响了更前面的孩子，需要连锁修正，一遍遍历根本搞不定。

教训：这种问题需要更系统的思考方式！

正确解法：分步骤思考

💡 核心思想：分而治之

既然一次搞定左右关系很困难，那我们就分两步：

第一步： 只考虑左边关系，从左到右遍历
第二步： 只考虑右边关系，从右到左遍历
最后： 每个位置取两种要求的最大值

方法一：两次遍历（推荐新手理解）

func candy(ratings []int) int {
    n := len(ratings)
    left := make([]int, n)  // 存储只考虑左边关系的结果
    
    // 🚶‍♂️ 第一次遍历：从左到右，只管左边邻居
    for i := 0; i < n; i++ {
        if i > 0 && ratings[i] > ratings[i-1] {
            left[i] = left[i-1] + 1  // 比左边多1颗
        } else {
            left[i] = 1  // 最少1颗
        }
    }
    
    // 🚶‍♀️ 第二次遍历：从右到左，只管右边邻居
    right := 1  // 当前位置从右边看需要的糖果数
    total := 0
    
    for i := n-1; i >= 0; i-- {
        if i < n-1 && ratings[i] > ratings[i+1] {
            right++  // 比右边多1颗
        } else {
            right = 1  // 最少1颗
        }
        
        // 🎯 关键：取两个要求的最大值
        total += max(left[i], right)
    }
    
    return total
}

让我们用例子 [1,0,2] 详细走一遍：

第一次遍历（从左到右）：

i=0: ratings[0]=1，第一个孩子，给1颗 → left[0]=1
i=1: ratings[1]=0 < ratings[0]=1，给1颗 → left[1]=1
i=2: ratings[2]=2 > ratings[1]=0，给2颗 → left[2]=2

结果：left = [1,1,2]

第二次遍历（从右到左）：

i=2: ratings[2]=2，最后一个孩子，给1颗 → right=1，total += max(2,1) = 2
i=1: ratings[1]=0 < ratings[2]=2，给1颗 → right=1，total += max(1,1) = 1，total=3
i=0: ratings[0]=1 > ratings[1]=0，给2颗 → right=2，total += max(1,2) = 2，total=5

最终结果： 5颗糖果，分配方案是 [2,1,2] ✅

方法二：一次遍历（高级技巧）

如果你已经理解了上面的方法，我们可以学习一个更巧妙的技巧：用"爬山"的思维来思考这个问题。

核心思想： 把评分序列想象成一座座山峰和山谷，我们要沿着山路分发糖果。

func candy(ratings []int) int {
    n := len(ratings)
    if n <= 1 {
        return n
    }
    
    total := 1       // 第一个孩子的糖果
    upSlope := 0     // 当前上坡的长度
    downSlope := 0   // 当前下坡的长度
    peakHeight := 0  // 山峰的高度（上坡长度）
    
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            // 📈 上坡：评分在上升
            downSlope = 0           // 重置下坡
            upSlope++               // 上坡长度+1
            peakHeight = upSlope    // 更新山峰高度
            total += upSlope + 1    // 当前孩子得到 upSlope+1 颗糖果
            
        } else if ratings[i] == ratings[i-1] {
            // ➡️ 平地：评分相等
            upSlope = 0     // 重置所有状态
            downSlope = 0
            peakHeight = 0
            total += 1      // 平地上只需要1颗糖果
            
        } else {
            // 📉 下坡：评分在下降
            upSlope = 0     // 重置上坡
            downSlope++     // 下坡长度+1
            total += downSlope  // 这是关键的一步！
            
            // 🏔️ 特殊处理：山峰可能需要更多糖果
            if peakHeight < downSlope {
                total += 1
            }
        }
    }
    
    return total
}

让我用爬山的比喻解释 total += downSlope 这个关键步骤：

想象你在一个下坡路段：[5, 4, 3, 2, 1]

按照规则，糖果应该这样分配：[5, 4, 3, 2, 1]

当我们走到最后一个孩子（评分1）时：

他需要1颗糖果
倒数第2个孩子需要2颗糖果
倒数第3个孩子需要3颗糖果
…

total += downSlope 巧妙地实现了这个分配：

给当前孩子1颗
同时给前面的每个孩子"补"1颗

山峰的特殊处理：

这是算法中最精妙的部分！让我详细解释为什么需要 total += 1 这个修正。

考虑这个例子：[1, 3, 2, 1]

1
2
3

  /\
 /  \
/    \

关键问题：山峰既是上坡的终点，也是下坡的起点！

让我们分步分析：

上坡阶段：山峰（评分3）因为上坡得到了 peakHeight + 1 = 2 颗糖果
下坡阶段：当我们处理下坡时
- 最右边的孩子（评分1）得到 1 颗糖果
- 倒数第2个孩子（评分2）需要比右边多，得到 2 颗糖果
- 山峰（评分3）需要比右边的孩子（评分2）多，至少需要 3 颗糖果

矛盾出现了！

山峰从上坡角度只得到了 2 颗糖果
但从下坡角度需要至少 3 颗糖果

算法是怎么发现和解决这个问题的？

// 当处理下坡时，downSlope = 2（下坡长度）
total += downSlope  // 这给下坡路径分配了糖果

// 检查山峰是否需要额外糖果
if peakHeight < downSlope {  // 1 < 2，条件成立
    total += 1  // 给山峰补1颗糖果
}

为什么补1颗就够了？

这里有个巧妙的数学关系：

山峰右边第一个孩子（下坡起点）现在有 downSlope 颗糖果
山峰需要比它多1颗，即需要 downSlope + 1 颗
山峰原来有 peakHeight + 1 颗
差值就是：(downSlope + 1) - (peakHeight + 1) = downSlope - peakHeight
当 peakHeight < downSlope 时，差值就是1！

用具体数字验证：

例子 [1, 3, 2, 1]：
- peakHeight = 1（上坡长度）
- downSlope = 2（下坡长度）
- 山峰原有糖果：1 + 1 = 2颗
- 山峰需要糖果：2 + 1 = 3颗
- 需要补充：3 - 2 = 1颗 ✅

这就是为什么 total += 1 这一行代码如此关键——它确保了山峰能同时满足左右两边的约束条件！

用具体例子演示整个过程

让我们用 [1, 3, 2, 1] 详细演示一次遍历的过程：

初始状态：
- total = 1 (第一个孩子)
- upSlope = 0, downSlope = 0, peakHeight = 0

i=1: ratings[1]=3 > ratings[0]=1 (上坡)
- downSlope = 0
- upSlope = 1
- peakHeight = 1  
- total += 2 (upSlope+1)
- total = 1 + 2 = 3

i=2: ratings[2]=2 < ratings[1]=3 (下坡)
- upSlope = 0
- downSlope = 1
- total += 1 (downSlope)
- total = 3 + 1 = 4
- peakHeight(1) < downSlope(1)? 否，不需要补充

i=3: ratings[3]=1 < ratings[2]=2 (继续下坡)  
- downSlope = 2
- total += 2 (downSlope)
- total = 4 + 2 = 6
- peakHeight(1) < downSlope(2)? 是！需要补充
- total += 1 = 7

最终：total = 7，对应分配 [1, 3, 2, 1]

复杂度对比

方法	时间复杂度	空间复杂度	理解难度	推荐指数
两次遍历	O(n)	O(n)	⭐⭐	⭐⭐⭐⭐⭐
一次遍历	O(n)	O(1)	⭐⭐⭐⭐	⭐⭐⭐

常见错误总结

1. 只考虑一个方向的约束

// ❌ 错误
if ratings[i] > ratings[i-1] {
    candies[i] = candies[i-1] + 1
} else {
    candies[i] = 1  // 这里没考虑右边邻居
}

2. 边界条件处理不当

// ❌ 忘记检查数组长度
// ❌ 数组下标越界
for i := 1; i <= n; i++ {  // 应该是 i < n
    // ...
}

3. 状态重置遗漏

// ❌ 在平地时忘记重置状态
if ratings[i] == ratings[i-1] {
    total += 1  // 只加了糖果，忘记重置状态变量
}

学到的经验

🎯 解题思路

分解问题： 复杂的双向约束 → 分别处理左右约束
贪心策略： 每个位置取满足所有约束的最小值
优化空间： 用状态变量代替额外数组

🔗 相关问题

LeetCode 42: 接雨水 - 也用到了"山峰山谷"的思想
LeetCode 84: 柱状图中最大的矩形 - 类似的单调性处理

💡 记忆口诀

“爬山分糖果，左右都要顾，分步来解决，贪心定最优”

这道题教会我们：看似复杂的问题，往往可以通过巧妙的分解和贪心策略来解决。关键是要找到正确的思考角度！ 🎉