每日算法练习：LeetCode 135. 分发糖果 ✅

大家好，我是你们的算法小伙伴。今天我们来练习一道经典的贪心算法题目 ——LeetCode 135. 分发糖果。这道题需要同时满足左右两边的约束，是面试中非常典型的 “两次遍历” 贪心问题。

题目描述

n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到1 个糖果。
• 相邻两个孩子中，评分更高的那个会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

示例 1：

输入：ratings = [1,0,2] 输出：5 解释：可以分别给三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2] 输出：4 解释：可以分别给三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，满足题目要求。

提示：

• n == ratings.length
• 1 <= n <= 2 * 10^4
• 0 <= ratings[i] <= 2 * 10^4

解题思路

核心约束拆解

我们需要同时满足两个方向的约束：

1. 从左到右：如果ratings[i] > ratings[i-1]，则candies[i] = candies[i-1] + 1。
2. 从右到左：如果ratings[i] > ratings[i+1]，则candies[i] = candies[i+1] + 1。

贪心策略：两次遍历

1. 第一次遍历（左→右）：先满足 “左边比我小，我要更多” 的约束，初始化每个孩子至少 1 颗糖果。
2. 第二次遍历（右→左）：再满足 “右边比我小，我要更多” 的约束，同时取两次遍历结果的最大值，保证同时满足两个方向的约束。
3. 求和：将所有孩子的糖果数相加，得到最少总数。

代码实现

class Solution { public int candy(int[] ratings) { int n = ratings.length; int[] candies = new int[n]; // 每个孩子至少 1 颗糖果 Arrays.fill(candies, 1); // 第一次遍历：左 → 右 for (int i = 1; i < n; i++) { if (ratings[i] > ratings[i-1]) { candies[i] = candies[i-1] + 1; } } // 第二次遍历：右 → 左 for (int i = n-2; i >= 0; i--) { if (ratings[i] > ratings[i+1]) { // 取最大值，保证同时满足左右约束 candies[i] = Math.max(candies[i], candies[i+1] + 1); } } // 计算总和 int total = 0; for (int c : candies) { total += c; } return total; } }

代码详解（结合示例 1 模拟）

示例 1：ratings = [1,0,2]

第一步：初始化

candies = [1, 1, 1]

第二步：左→右遍历

• i=1：ratings[1]=0 < ratings[0]=1→ 不变化，candies = [1, 1, 1]
• i=2：ratings[2]=2 > ratings[1]=0→candies[2] = 1+1=2，candies = [1, 1, 2]

第三步：右→左遍历

• i=1：ratings[1]=0 < ratings[2]=2→ 不变化，candies = [1, 1, 2]
• i=0：ratings[0]=1 > ratings[1]=0→candies[0] = max(1, 1+1)=2，candies = [2, 1, 2]

第四步：求和

2 + 1 + 2 = 5，与示例结果一致。

复杂度分析

• 时间复杂度：O (n)，两次遍历数组，一次求和，共 O (3n) = O (n)。
• 空间复杂度：O (n)，需要额外数组candies存储每个孩子的糖果数。

总结

1. 核心思想：通过两次遍历分别处理左右约束，最后取最大值，保证同时满足所有条件。
2. 贪心本质：每次只关注当前方向的最优解，最终合并得到全局最优解。
3. 易错点：第二次遍历时必须取max，否则会破坏第一次遍历已经满足的约束。

这道题是贪心算法中 “多方向约束” 的经典应用，理解两次遍历的逻辑，就能轻松解决这类问题。

今天的每日算法练习就到这里，我们明天再见！👋