LeetCode 135. Candy 题解题目描述老师想给孩子们分发糖果有 N 个孩子站成了一条直线老师会根据每个孩子的表现预先给他们评分。你需要按照以下要求帮助老师给这些孩子分发糖果每个孩子至少分配到 1 个糖果。评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。那么这样下来老师至少需要准备多少颗糖果呢示例 1输入[1,0,2] 输出5 解释你可以分别给这三个孩子分发 2、1、2 颗糖果。示例 2输入[1,2,2] 输出4 解释你可以分别给这三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果这已满足上述两个条件。解题思路方法贪心算法思路贪心算法的核心思想是在每一步选择中都采取在当前状态下最好或最优的选择从而希望导致结果是全局最好或最优的。对于这个问题我们可以从左到右遍历数组确保每个孩子比左边的孩子获得更多的糖果如果评分更高。从右到左遍历数组确保每个孩子比右边的孩子获得更多的糖果如果评分更高。取两次遍历的最大值得到每个孩子最终的糖果数。计算所有孩子的糖果数之和。复杂度分析时间复杂度O(n)其中 n 是孩子的数量。需要遍历数组两次。空间复杂度O(n)需要使用一个数组来存储每个孩子的糖果数。代码实现方法贪心算法class Solution: def candy(self, ratings: List[int]) - int: # 初始化糖果数组每个孩子至少有 1 颗糖果 n len(ratings) candies [1] * n # 从左到右遍历确保每个孩子比左边的孩子获得更多的糖果 for i in range(1, n): if ratings[i] ratings[i-1]: candies[i] candies[i-1] 1 # 从右到左遍历确保每个孩子比右边的孩子获得更多的糖果 for i in range(n-2, -1, -1): if ratings[i] ratings[i1]: candies[i] max(candies[i], candies[i1] 1) # 计算所有孩子的糖果数之和 return sum(candies)测试用例测试用例 1输入[1,0,2]输出5测试用例 2输入[1,2,2]输出4总结本题是贪心算法的经典问题主要考察对贪心算法思想的理解和应用。通过两次遍历数组我们可以高效地计算出每个孩子应该获得的糖果数。贪心算法的核心思想是在每一步选择中都采取在当前状态下最好或最优的选择从而希望导致结果是全局最好或最优的。这种方法不仅适用于分发糖果问题还可以应用于许多其他需要局部最优选择的问题。掌握贪心算法的原理对于理解算法设计思想非常重要。