Vue.js

Appearance

On this page

实战：分发糖果 ​

LeetCode 135. 分发糖果 | 难度：困难

两端贪心的经典应用，体现了"分解约束、逐一满足"的思想。

📎 LeetCode 135. 分发糖果

题目描述 ​

n 个孩子站成一排，每个孩子有一个评分。按照以下规则分发糖果：

  1. 每个孩子至少得到 1 颗糖果
  2. 评分更高的孩子比相邻孩子获得更多糖果

求最少需要多少颗糖果。

示例1：

输入：ratings = [1,0,2]
输出：5
解释：分配 [2,1,2]

示例2：

输入：ratings = [1,2,2]
输出：4
解释：分配 [1,2,1]，第三个孩子评分不比第二个高，只需1颗

问题分析 ​

约束条件 ​

每个孩子 i 要同时满足两个约束：

  • 左约束：如果 ratings[i] > ratings[i-1]，则 candies[i] > candies[i-1]
  • 右约束：如果 ratings[i] > ratings[i+1]，则 candies[i] > candies[i+1]

难点 ​

如果只从一个方向考虑，无法同时满足左右约束。

核心思路：分别满足左右约束，最后合并。

解法：两次遍历 ​

思路 ​

  1. 从左到右：保证右边评分更高的孩子比左边邻居糖果更多
  2. 从右到左：保证左边评分更高的孩子比右边邻居糖果更多
  3. 取最大值：每个位置取两次遍历结果的最大值

代码实现 ​

typescript
function candy(ratings: number[]): number {
  const n = ratings.length;
  if (n === 0) return 0;
  
  const candies = new Array(n).fill(1);
  
  // 从左到右：处理上坡（满足左约束）
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }
  
  // 从右到左：处理下坡（满足右约束）
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
      // 取最大值：同时满足左右约束
      candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }
  }
  
  return candies.reduce((a, b) => a + b, 0);
}

执行过程详解 ​

以 ratings = [1, 2, 87, 87, 87, 2, 1] 为例：

初始化（每人至少1颗）：
candies = [1, 1, 1, 1, 1, 1, 1]

第一次遍历：从左到右（满足左约束）
i=1: 2>1,  candies[1] = candies[0]+1 = 2
     → [1, 2, 1, 1, 1, 1, 1]

i=2: 87>2, candies[2] = candies[1]+1 = 3
     → [1, 2, 3, 1, 1, 1, 1]

i=3: 87=87, 不满足条件，不变
i=4: 87=87, 不满足条件，不变
i=5: 2<87, 不满足条件，不变
i=6: 1<2, 不满足条件，不变

第一次结果：[1, 2, 3, 1, 1, 1, 1]
（只满足了左约束）

第二次遍历：从右到左（满足右约束）
i=5: 2>1, candies[5] = max(1, 1+1) = 2
     → [1, 2, 3, 1, 1, 2, 1]

i=4: 87>2, candies[4] = max(1, 2+1) = 3
     → [1, 2, 3, 1, 3, 2, 1]

i=3: 87=87, 不满足条件，不变
i=2: 87=87, 不满足条件，不变
i=1: 2<87, 不满足条件，不变
i=0: 1<2, 不满足条件，不变

最终结果：[1, 2, 3, 1, 3, 2, 1]
总计：1+2+3+1+3+2+1 = 13

为什么取 max？ ​

第二次遍历不能直接覆盖，因为可能破坏第一次已满足的约束。

例如：ratings = [1, 2, 3]

第一次（左→右）: [1, 2, 3]  ← 正确
第二次（右→左）: 无需改变

如果第二次直接覆盖（不取 max）:
  i=1: 2<3，不满足 ratings[i]>ratings[i+1]
  结果保持 [1, 2, 3]，正确

但如果 ratings = [3, 2, 1]:
  第一次: [1, 1, 1]
  第二次: [3, 2, 1]，正确

如果 ratings = [1, 3, 2, 1]:
  第一次: [1, 2, 1, 1]
  第二次从右到左:
    i=2: 2>1, candies[2] = max(1, 2) = 2 → [1, 2, 2, 1]
    i=1: 3>2, candies[1] = max(2, 3) = 3 → [1, 3, 2, 1]
    
  必须取 max！否则会破坏第一次的结果

正确性证明 ​

为什么两次遍历能满足所有约束？ ​

第一次遍历后：对于所有 i，如果 ratings[i] > ratings[i-1]，则 candies[i] > candies[i-1] ✓

第二次遍历后：

  • 取 max 保证了第一次的约束不被破坏
  • 同时，如果 ratings[i] > ratings[i+1]，则 candies[i] = max(..., candies[i+1]+1) ≥ candies[i+1]+1 ✓

结论：两个约束都被满足。

为什么是最小值？ ​

两次遍历都采用贪心策略：只在必要时增加糖果数。

  • 每次 +1 是满足约束的最小增量
  • 取 max 是同时满足两个约束的最小值

复杂度分析 ​

  • 时间复杂度：O(n)

    • 两次遍历，每次 O(n)

  • 空间复杂度：O(n)

    • 存储 candies 数组

空间优化：单次遍历 ​

通过记录"上坡"和"下坡"的长度，可以实现 O(1) 空间：

typescript
function candyOptimized(ratings: number[]): number {
  const n = ratings.length;
  if (n <= 1) return n;
  
  let candies = 1;  // 第一个孩子
  let up = 0;       // 上坡长度
  let down = 0;     // 下坡长度
  let peak = 0;     // 峰值高度
  
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
      // 上坡
      up++;
      down = 0;
      peak = up;
      candies += 1 + up;  // 当前孩子糖果数 = 1 + up
    } else if (ratings[i] < ratings[i - 1]) {
      // 下坡
      up = 0;
      down++;
      // 如果下坡超过峰值，峰值需要额外加1
      candies += 1 + down + (down > peak ? 1 : 0);
    } else {
      // 平坡
      up = down = peak = 0;
      candies += 1;
    }
  }
  
  return candies;
}

为什么下坡需要检查 peak？ ​

当下坡长度超过峰值时，峰值点需要额外增加糖果：

ratings: [1, 5, 4, 3, 2]
         ↗   ↘ ↘ ↘ ↘

上坡：[1] → [1, 2] （peak = 1）
下坡开始，按序：
  [1, 2, 1]
  [1, 2, 2, 1]  ← 此时下坡长度=2 > peak=1，峰值需要变成3
  [1, 3, 2, 1]
  [1, 4, 3, 2, 1]

常见错误 ​

错误1：只遍历一次 ​

typescript
// ❌ 错误：无法同时满足左右约束
for (let i = 1; i < n; i++) {
  if (ratings[i] > ratings[i - 1]) {
    candies[i] = candies[i - 1] + 1;
  }
  if (ratings[i] > ratings[i + 1]) {
    candies[i] = Math.max(candies[i], candies[i + 1] + 1);
  }
}
// 问题：candies[i+1] 还没有确定最终值

错误2：第二次遍历直接覆盖 ​

typescript
// ❌ 错误：可能破坏第一次的结果
if (ratings[i] > ratings[i + 1]) {
  candies[i] = candies[i + 1] + 1;  // 应该用 max
}

错误3：忽略相等情况 ​

typescript
// ❌ 错误：相等时也尝试增加
if (ratings[i] >= ratings[i - 1]) {  // 应该是 >
  candies[i] = candies[i - 1] + 1;
}
// ratings = [1, 2, 2] 会得到 [1, 2, 3]，但正确答案是 [1, 2, 1]

相关问题 ​

问题变体：评分相同也要不同糖果 ​

如果评分相同的相邻孩子也要分配不同数量的糖果，该如何处理？

思路：在相等时也需要满足约束，可以交替分配 1 和 2。

相关题目 ​

  • LeetCode 134. 加油站（环形贪心）
  • LeetCode 330. 按要求补齐数组

总结 ​

分发糖果展示了两端贪心的经典模式：

  1. 分解约束：左约束和右约束分开处理
  2. 两次遍历：先满足一个方向的约束，再满足另一个
  3. 取最大值：合并时保证两个约束都满足

核心思想：当单向遍历无法同时满足多个约束时，尝试多次遍历，每次专注于一个约束，最后合并结果。

在 GitHub 上编辑此页