首页 > 代码库 > LeetCode 135 Candy(贪心算法）
LeetCode 135 Candy(贪心算法）
135. Candy
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
要求使用最少的糖分给不同孩子，要注意只是有更高分数的拿更多的糖，相同分数可以给不同数量的糖。
考虑对第 i 个孩子，如果他的分数等于之前的孩子，那给他一颗糖就能满足条件。如果他的分数大于之前的孩子，给他前一个孩子的糖+1。如果小于，考虑给一颗糖，如果上一个孩子有不止一颗糖，可以满足条件，但是如果上一个孩子只有一颗糖，对上一个孩子来说，他有比右边孩子更高的分数，但是只有相同的糖的数目。所以这种情况需要重新考虑。
一个方法是对 i 之前的孩子遍历，依次增多糖的数目直到满足条件，但是这样复杂度达到O(n^2)，后面的case会超时。所以只能改变思路，一旦发现这样的 i ，我们从 i 开始找到分数最长连续递减的序列。比如 [1,4,3,2,1] 里，遍历到 2 时，糖果分配情况是
1,2,1 我们从 2 开始 找到递减序列 2,1 然后从 1 开始倒着对少分糖的孩子发糖，得到正确的分糖情况 [1,4,3,2,1] 。最后考虑一下边界即可。
python AC代码：
class Solution(object): def candy(self, ratings): can = [1 for _ in ratings] i = 1 while i<len(ratings): if ratings[i]==ratings[i-1]: i+=1 elif ratings[i]>ratings[i-1]: can[i]=can[i-1]+1 i+=1 else: if can[i-1]==1: while i+1<len(ratings) and ratings[i+1]<ratings[i]: i+=1 j = i while j-1>=0 and ratings[j-1]>ratings[j] and can[j-1]<=can[j]: can[j-1]=1+can[j] j-=1 if j>0 and ratings[j-1]<ratings[j] and can[j-1]>=can[j]: can[j] = can[j-1]+1 else: i+=1 return sum(can)
LeetCode 135 Candy(贪心算法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。