❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！
- 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
- 导航：
- LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
- 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
- python源码解读：解读python的源代码与调用关系，快速提升代码质量
- python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
题目描述
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：
- 每个孩子至少分到一个糖果。
- 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
你需要最少准备多少糖果。
示例 1:
输入: [1,0,2] 输出: 5 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:
输入: [1,2,2] 输出: 4 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这满足题目要求。
方法一：两次遍历法
解题步骤
- 创建一个糖果数组，初始化每个孩子的糖果数为 1。
- 从左到右遍历，如果当前孩子的评分高于前一个孩子，则当前孩子的糖果数设置为前一个孩子的糖果数加一。
- 从右到左遍历，如果当前孩子的评分高于后一个孩子，并且当前孩子的糖果数不大于后一个孩子的糖果数，则当前孩子的糖果数设置为后一个孩子的糖果数加一。
- 返回糖果数组的总和。
Python 示例
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] and candies[i] <= candies[i + 1]: candies[i] = candies[i + 1] + 1 return sum(candies) # Example usage ratings = [1, 0, 2] print(candy(ratings)) # Output: 5 ratings = [1, 2, 2] print(candy(ratings)) # Output: 4
算法分析
- 时间复杂度：O(N)，其中 N 是孩子的数量。需要遍历两次数组。
- 空间复杂度：O(N)，用于存储糖果数量的数组。
算法图解与说明
考虑 ratings = [1, 0, 2] 初始化糖果数组：candies = [1, 1, 1] 左到右遍历： 索引1: 1 (评分 0) <= 0 (评分 1), 无变化 索引2: 2 (评分 2) > 0 (评分 0), 更新 candies[2] = candies[1] + 1 = 2 结果: candies = [1, 1, 2] 右到左遍历： 索引1: 0 (评分 1) > 0 (评分 1) 且 candies[1] <= candies[2], 无变化 索引0: 1 (评分 1) > 0 (评分 0), 更新 candies[0] = candies[1] + 1 = 2 结果: candies = [2, 1, 2] 总糖果数: 2 + 1 + 2 = 5
方法二：单次遍历法
解题步骤
- 创建一个糖果数组，初始化每个孩子的糖果数为 1。
- 使用一个标记数组来记录相邻孩子之间的关系（评分高的标记为 1，评分低的标记为 -1，相等标记为 0）。
- 单次遍历，根据标记调整糖果数，确保所有条件都满足。
- 返回糖果数组的总和。
Python 示例
def candy(ratings): n = len(ratings) if n == 0: return 0 if n == 1: return 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) # Example usage ratings = [1, 0, 2] print(candy(ratings)) # Output: 5 ratings = [1, 2, 2] print(candy(ratings)) # Output: 4
算法分析
- 时间复杂度：O(N)，其中 N 是孩子的数量。需要遍历两次数组。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
算法图解与说明
考虑 ratings = [1, 0, 2] 初始化糖果数组：candies = [1, 1, 1] 单次遍历： 从左到右遍历： 索引1: 1 (评分 0) <= 0 (评分 1), 无变化 索引2: 2 (评分 2) > 0 (评分 0), 更新 candies[2] = candies[1] + 1 = 2 结果: candies = [1, 1, 2] 从右到左遍历： 索引1: 0 (评分 1) > 0 (评分 1) 且 candies[1] <= candies[2], 无变化 索引0: 1 (评分 1) > 0 (评分 0), 更新 candies[0] = candies[1] + 1 = 2 结果: candies = [2, 1, 2] 总糖果数: 2 + 1 + 2 = 5
这两种方法都能有效地解决分发糖果的问题，确保每个孩子至少得到一颗糖果，并且评分更高的孩子比相邻孩子获得更多糖果。选择哪种方法可以根据具体场景和个人喜好而定。
🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)
❤️❤️作者知识有限，如有错误，请各位大佬评论区批评指正，不胜感激❥(^_-)
