LeetCode 分发糖果II题解

LeetCode 分发糖果II题解

题目描述

老师要给孩子们分发糖果。但是，如果一个孩子的评分比他相邻的孩子的评分高，他必须获得比相邻孩子更多的糖果。请问老师至少要准备多少糖果？

示例：

输入：ratings = [1,0,2]
输出：5

解题思路

方法：贪心

思路：

• 使用贪心算法，两次遍历。
• 第一次从左到右遍历，确保每个孩子的糖果数比左边的孩子多。
• 第二次从右到左遍历，确保每个孩子的糖果数比右边的孩子多。
• 取两次遍历结果的最大值。

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。

代码实现

def candy(ratings): 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[i+1]: candies[i] = max(candies[i], candies[i+1] + 1) return sum(candies) # 测试 def test_candy(): ratings = [1, 0, 2] print(candy(ratings)) # 输出：5 if __name__ == "__main__": test_candy()

总结

分发糖果II是贪心算法的典型应用，通过两次遍历来确保每个孩子的糖果数比相邻的孩子多。