大家好我是你们的算法小伙伴。今天我们来练习一道经典的贪心算法题目 ——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.length1 n 2 * 10^40 ratings[i] 2 * 10^4解题思路核心约束拆解我们需要同时满足两个方向的约束从左到右如果ratings[i] ratings[i-1]则candies[i] candies[i-1] 1。从右到左如果ratings[i] ratings[i1]则candies[i] candies[i1] 1。贪心策略两次遍历第一次遍历左→右先满足 “左边比我小我要更多” 的约束初始化每个孩子至少 1 颗糖果。第二次遍历右→左再满足 “右边比我小我要更多” 的约束同时取两次遍历结果的最大值保证同时满足两个方向的约束。求和将所有孩子的糖果数相加得到最少总数。代码实现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[i1]) { // 取最大值保证同时满足左右约束 candies[i] Math.max(candies[i], candies[i1] 1); } } // 计算总和 int total 0; for (int c : candies) { total c; } return total; } }代码详解结合示例 1 模拟示例 1ratings [1,0,2]第一步初始化candies [1, 1, 1]第二步左→右遍历i1ratings[1]0 ratings[0]1→ 不变化candies [1, 1, 1]i2ratings[2]2 ratings[1]0→candies[2] 112candies [1, 1, 2]第三步右→左遍历i1ratings[1]0 ratings[2]2→ 不变化candies [1, 1, 2]i0ratings[0]1 ratings[1]0→candies[0] max(1, 11)2candies [2, 1, 2]第四步求和2 1 2 5与示例结果一致。复杂度分析时间复杂度O (n)两次遍历数组一次求和共 O (3n) O (n)。空间复杂度O (n)需要额外数组candies存储每个孩子的糖果数。总结核心思想通过两次遍历分别处理左右约束最后取最大值保证同时满足所有条件。贪心本质每次只关注当前方向的最优解最终合并得到全局最优解。易错点第二次遍历时必须取max否则会破坏第一次遍历已经满足的约束。这道题是贪心算法中 “多方向约束” 的经典应用理解两次遍历的逻辑就能轻松解决这类问题。今天的每日算法练习就到这里我们明天再见
每日算法练习：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.length1 n 2 * 10^40 ratings[i] 2 * 10^4解题思路核心约束拆解我们需要同时满足两个方向的约束从左到右如果ratings[i] ratings[i-1]则candies[i] candies[i-1] 1。从右到左如果ratings[i] ratings[i1]则candies[i] candies[i1] 1。贪心策略两次遍历第一次遍历左→右先满足 “左边比我小我要更多” 的约束初始化每个孩子至少 1 颗糖果。第二次遍历右→左再满足 “右边比我小我要更多” 的约束同时取两次遍历结果的最大值保证同时满足两个方向的约束。求和将所有孩子的糖果数相加得到最少总数。代码实现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[i1]) { // 取最大值保证同时满足左右约束 candies[i] Math.max(candies[i], candies[i1] 1); } } // 计算总和 int total 0; for (int c : candies) { total c; } return total; } }代码详解结合示例 1 模拟示例 1ratings [1,0,2]第一步初始化candies [1, 1, 1]第二步左→右遍历i1ratings[1]0 ratings[0]1→ 不变化candies [1, 1, 1]i2ratings[2]2 ratings[1]0→candies[2] 112candies [1, 1, 2]第三步右→左遍历i1ratings[1]0 ratings[2]2→ 不变化candies [1, 1, 2]i0ratings[0]1 ratings[1]0→candies[0] max(1, 11)2candies [2, 1, 2]第四步求和2 1 2 5与示例结果一致。复杂度分析时间复杂度O (n)两次遍历数组一次求和共 O (3n) O (n)。空间复杂度O (n)需要额外数组candies存储每个孩子的糖果数。总结核心思想通过两次遍历分别处理左右约束最后取最大值保证同时满足所有条件。贪心本质每次只关注当前方向的最优解最终合并得到全局最优解。易错点第二次遍历时必须取max否则会破坏第一次遍历已经满足的约束。这道题是贪心算法中 “多方向约束” 的经典应用理解两次遍历的逻辑就能轻松解决这类问题。今天的每日算法练习就到这里我们明天再见
