LeetCode 135. 分发糖果（Candy） 是一道经典的贪心算法题，要求在满足两个条件的前提下，分配最少的糖果总数：

📌 题目要求

给定一个整数数组 ratings，表示一排孩子的评分。你需要分发糖果，满足：

1. 每个孩子至少分到 1 颗糖果；
2. 相邻孩子中，评分更高的孩子必须比邻居获得更多糖果。

注意：相等评分的孩子之间 没有糖果数量约束。

返回 最少需要准备的糖果总数。

✅ 示例

输入: ratings =
输出: 5
解释: 分配

输入: ratings =
输出: 4
解释: 分配

🧠 解题思路：两次遍历（贪心）

关键在于：每个孩子的糖果数受左右两侧同时影响。
因此不能只从左或只从右处理，而要 分别满足“左规则”和“右规则”，再取最大值。

拆解规则：

• 左规则：如果 ratings[i] > ratings[i-1]，则 candy[i] > candy[i-1]
• 右规则：如果 ratings[i] > ratings[i+1]，则 candy[i] > candy[i+1]

最终每个孩子的糖果数 = 同时满足左、右规则的最小值 → 即 max(左规则结果, 右规则结果)

✅ 算法步骤

1. 初始化 candy[] 数组，每个孩子先分 1 颗糖。
2. 从左往右遍历：
   • 若 ratings[i] > ratings[i-1]，则 candy[i] = candy[i-1] + 1
3. 从右往左遍历：
   • 若 ratings[i] > ratings[i+1]，则 candy[i] = max(candy[i], candy[i+1] + 1)
4. 求和 candy[] 返回。

✅ Java 实现（标准解法）

public int candy(int[] ratings) {
int n = ratings.length;
if (n == 0) return 0;

int[] candy = new int[n];
// Step 1: 每人至少1颗
for (int i = 0; i  ratings[i - 1]) {
        candy[i] = candy[i - 1] + 1;
    }
}

// Step 3: 从右到左，满足右规则
for (int i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
        candy[i] = Math.max(candy[i], candy[i + 1] + 1);
    }
}

// Step 4: 求和
int total = 0;
for (int c : candy) {
    total += c;
}
return total;

}

⚡ 优化：空间 O(1)（一次遍历）

虽然存在 O(1) 空间的一次遍历解法（通过记录递增/递减段长度），但逻辑复杂且易错。两次遍历法是面试中最推荐的写法：清晰、高效、不易出错。

📊 复杂度分析

• 时间复杂度：O(n) —— 三次线性遍历
• 空间复杂度：O(n) —— 存储 candy[] 数组

✅ 正确性说明

• 第一次遍历确保：所有“比左边高”的孩子糖果更多
• 第二次遍历确保：所有“比右边高”的孩子糖果更多
• 使用 Math.max 保证：不破坏第一次的结果，同时满足右侧约束

例如 ratings = ：

• 初始：
• 左→右后：（第三个 2 不大于前一个 2，保持 1）
• 右→左：检查 ，无变化
• 总和 = 4 ✅

如需 Python / C++ 版本，或想了解 O(1) 空间解法，也可以告诉我！