LeetCode 135：分糖果

LeetCode 135：分糖果

问题本质与核心挑战

给定孩子的评分数组，需满足 “每个孩子至少1颗糖果，相邻评分高的孩子糖果更多”，求最少糖果总数。核心挑战：

• 相邻约束是双向的（左→右和右→左都需满足），直接枚举无法高效解决；
• 需通过 两次贪心遍历（左→右、右→左）分别处理单向约束，再合并结果。

核心思路：双向贪心 + 合并约束

1. 单向约束处理（左→右遍历）

• 定义数组 left，left[i] 表示 从左到右遍历 时，第 i 个孩子应得的最少糖果（仅满足“左边约束”：若 ratings[i] > ratings[i-1]，则 left[i] = left[i-1]+1；否则为 1）。

2. 单向约束处理（右→左遍历）

• 定义数组 right，right[i] 表示 从右到左遍历 时，第 i 个孩子应得的最少糖果（仅满足“右边约束”：若 ratings[i] > ratings[i+1]，则 right[i] = right[i+1]+1；否则为 1）。

3. 合并双向约束

• 每个孩子最终的糖果数为 max(left[i], right[i])（同时满足左右约束），求和即为答案。

算法步骤详解（以示例 ratings = [1,0,2] 为例）

步骤 1：左→右遍历，处理左边约束

步骤 2：右→左遍历，处理右边约束

步骤 3：合并约束，计算总和

完整代码（Java）

class Solution {public int candy(int[] ratings) {int n = ratings.length;if (n == 0) return 0; // 边界处理（题目保证n≥1，可省略）// 1. 左→右遍历，处理左边约束int[] left = new int[n];left[0] = 1; // 第一个孩子至少1颗for (int i = 1; i < n; i++) {if (ratings[i] > ratings[i-1]) {left[i] = left[i-1] + 1;} else {left[i] = 1;}}// 2. 右→左遍历，处理右边约束int[] right = new int[n];right[n-1] = 1; // 最后一个孩子至少1颗for (int i = n-2; i >= 0; i--) {if (ratings[i] > ratings[i+1]) {right[i] = right[i+1] + 1;} else {right[i] = 1;}}// 3. 合并双向约束，计算总和int total = 0;for (int i = 0; i < n; i++) {total += Math.max(left[i], right[i]);}return total;}
}

关键逻辑解析

1. 左→右遍历：确保 “右边孩子评分更高时，糖果数比左边多”，但无法处理“左边孩子评分更高，右边需更多”的情况（如 [5,4,3,2,1]，左遍历后所有 left[i]=1，需右遍历修正）。
2. 右→左遍历：确保 “左边孩子评分更高时，糖果数比右边多”，与左遍历互补。
3. 合并约束：取两者最大值，保证同时满足左右双向约束，且糖果数最少（贪心思想：仅在必要时增加糖果）。

复杂度分析

• 时间复杂度：O(n)（两次遍历数组，每次 O(n)，合并遍历 O(n)）。
• 空间复杂度：O(n)（存储 left 和 right 数组，可优化为 O(1)，但代码可读性降低）。

该方法通过 两次贪心遍历拆分双向约束，将复杂的双向问题转化为两个单向问题，再合并求解，确保了效率和可读性的平衡，是处理此类“双向约束”问题的经典思路。