Python|贪心的分发糖果
问题描述
分发糖果（力扣135）：
老师想给孩子们分发糖果，有N个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
解决方案
规则：相邻的孩子中，评分高的孩子必须获得更多的糖果。
通俗的讲，评分为2的孩子得到了1个，相邻的评分为3的孩子最少得到2个。要注意的是：满足规则且糖果总数最少的情况下，相邻的两个评分相同的孩子得到的糖果数量是不同的（比如上面的示例2）。
根据这个规则并且题目要求糖果总数最少，就可以利用贪心思想，在遍历过程中，每一步都尽量少给糖（给评分高的人一个满足规则，给两个也满足规则。但最优的话就是只给一个），按照规则一定要加的时候才加一个，不违背规则的时候就一定不能加。
思路：为了更容易理清思路，可以兵分两路，从左到右和从右到左分别考虑。这样先找从左到右满足规则最少的糖果，再找从右到左的，最后取两边都满足的值，也就是最大值，然后相加之和就是所求最少糖果总数。
题目代码：
class Solution: def candy(self, ratings: List[int]) -> int: # 记录从左到右按规则每个孩子所得最少糖果 r = [1] * len(ratings) # 记录从右到左按规则每个孩子所得最少糖果 l = r.copy() for i in range(1, len(ratings)): # 从左到右开始添加糖果数量 if ratings[i] > ratings[i-1]: r[i] = r[i-1] + 1 # 从右到左开始添加糖果数量 if ratings[-i-1] > ratings[-i]: l[-i-1] = l[-i] + 1 # 最后取最大值的相加之和 return sum([max(a, b) for a, b in zip(r, l)]) |
|---|
结语
题目要求的是糖果总和最小，就可以利用贪心算法局部最优的选择，即贪心选择来达到。贪心算法的基本思路就是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。
END
主 编 | 王文星
责 编 | 周茂林