这里写自定义目录标题
- 题目
- 解题
- 问题描述
- 解题思路
- 详细步骤
- 初始化
- 左到右扫描
- 右到左扫描
- 计算总糖果
- Python 代码示例
- 示例
- 示例 1
- 示例 2
- 复杂度分析
题目
仅供学习
解题
使用一种贪心算法的策略解决糖果分配问题。
问题描述
给定一个整数数组 ratings,表示每个孩子的评分。需要满足以下条件分配糖果:
- 每个孩子至少分配到 1 个糖果。
- 相邻两个孩子中,评分更高的孩子会获得更多的糖果。
解题思路
- 初始化糖果数组:首先,给每个孩子分配 1 个糖果。
- 从左到右扫描:确保评分较高的孩子获得比其左边的孩子更多的糖果。
- 从右到左扫描:确保评分较高的孩子获得比其右边的孩子更多的糖果。
- 计算总糖果:合并以上两个扫描结果,得到每个孩子的最小糖果需求。
详细步骤
初始化
- 创建一个与 ratings 数组长度相同的 candies 数组,每个值初始化为 1。
左到右扫描
- 从左到右扫描 ratings 数组,如果当前孩子的评分高于前一个孩子的评分,则当前孩子的糖果数应比前一个孩子的糖果数多 1。
右到左扫描
- 从右到左扫描 ratings 数组,如果当前孩子的评分高于后一个孩子的评分,则当前孩子的糖果数应比后一个孩子的糖果数多 1。
计算总糖果
- 求 candies 数组的总和,即为所需的最少糖果数。
Python 代码示例
def candy(ratings):n = len(ratings)if n == 0:return 0# 每个孩子最少分配 1 个糖果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)
示例
示例 1
- 输入:ratings = [1,0,2]
- 输出:5
- 解释:可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2
- 输入:ratings = [1,2,2]
- 输出:4
- 解释:可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
复杂度分析
- 时间复杂度:O(n),其中 n 是数组 ratings 的长度,因为我们需要遍历数组两次。
- 空间复杂度:O(n),用于存储 candies 数组。