【LeetCode】贪心算法--分发糖果（135）

写在前面

期末考试结束了，公众号今天恢复更新，这是19年第一篇技术文。大学的期末考试经历了很多次，第一次这么认真的准备，当然是因为对自己的要求提高了，之前只想着及格就OK，这次对自己的要求是每科都90+（已经有一科完成这个小目标了）在Python考试中暴露了自己之前学习过程中的很多问题，所以打算这个寒假将之前自己所写的Python教程进行一次复盘，公众号会提供更加优秀的Python教程，同时还会对机器学习做一个简单的知识讲解，这个假期重点放在数据结构和算法上，大部分的推文会是LeetCode刷题和PTA刷题。今天这篇文章是贪心算法系列的第二篇--分发糖果。

前文回顾：

【LeetCode】贪心算法--买卖股票的最佳时机 II（122）

刷题汇总：

【LeetCode】汇总贴（NO.1-20）

今日题目

老师想给孩子们分发糖果，有N个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。 你需要按照以下要求，帮助老师给这些孩子分发糖果： 每个孩子至少分配到 1 个糖果。相邻的孩子中，评分高的孩子必须获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1: 输入: [1,0,2] 输出: 5 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。 示例 2: 输入: [1,2,2] 输出: 4 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

题目分析

对于这个问题，主要的条件是要相邻孩子，得分高的拿的糖果要多（不包括相等得分），还有就是每个人最少都要有一个。 解决这个问题我们还是采用贪心算法，首先初始化每个人分配的糖果数量都是1，然后这个算法需要遍历两遍，第一遍从左往右遍历，如果当前孩子的分数大于前一个孩子的分数，则当前孩子得到的糖果在前一个孩子的基础上加1；然后，第二遍从右往左遍历，如果当前孩子的分数大于他右边孩子的分数，并且他的糖果不比他右边孩子多，则糖果数在他基础上加1；最后，将所有孩子的糖果数相加即可。 第二次遍历是为了处理数组中降序和有出现相邻孩子分数相同的情况。

代码实现

 1class Solution:
 2    def candy(self, ratings):
 3        """
 4        :type ratings: List[int]
 5        :rtype: int
 6        """
 7        num = [1]*len(ratings)
 8        for i in range(0,len(ratings)-1):
 9            if ratings[i+1] > ratings[i]:
10                num[i+1] = num[i] + 1     
11        for i in range(len(ratings)-1,0,-1):
12            if ratings[i] < ratings[i-1]:
13                num[i-1] = max(num[i]+1,num[i-1])
14
15        return sum(num)

写在最后

寒假已经跟一个小伙伴商量好一起刷题，感兴趣的小伙伴也可以加入我们，希望大家每天可以交流刷题的心得，为了保证质量我会控制人数，大约在12人左右。