2018年10月28日
#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?
样例：
Example 1:Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.The third child gets 1 candy because it satisfies the above two conditions.
问题分析：
本题难度为Hard！已给出的函数定义为：
class Solution:def candy(self, ratings):""":type ratings: List[int]:rtype: int"""其中参数ratings为列表，输出为int类型；
该题属于 贪心问题，有很多种解法，这里采取一种最好理解的方法；本题的题目要求是若一个小孩的评分比相邻的小孩的评分高，那么他的所获得的糖果就必须比相邻的小孩多，且每个小孩至少获得一颗糖果，求最少要分配多少颗糖果。
这里首先考虑一种更简单一点的情况，即从第一个小孩开始，只要求如果一个小孩的评分比前一个小孩的评分高，则他获得的糖果比前一个小孩多，这样每个小孩获得的糖果都比其 前相邻 的小孩获得的糖果多；这样只需要遍历一次ratings，每次遇到小孩的评分比前一个小孩的评分高，则他获得的糖果是前一个小孩的糖果数加一。
同理，反方向进行判断，从最后一个小孩开始，若一个小孩的评分比后一个小孩的评分高，则他获得的糖果比后一个小孩多，这样每个小孩获得的糖果都比其 后相邻 的小孩获得的糖果多，实现方法同前反向遍历即可。
这样将两种情况结合起来，一个小孩最终获得的糖果取前相邻和后相邻情况的较大值。
代码实现：
python3
#coding:utf-8
class Solution:def candy(self, ratings):""":type ratings: List[int]:rtype: int"""forward_candy=[1 for i in range(len(ratings))]backward_candy=[1 for i in range(len(ratings))]final_candy = [0 for i in range(len(ratings))]for i in range(len(ratings)-1):if ratings[i+1]>ratings[i]: # forwardforward_candy[i+1]=forward_candy[i]+1if ratings[len(ratings)-2-i]>ratings[len(ratings)-1-i]: # backwardbackward_candy[len(ratings)-2-i]=backward_candy[len(ratings)-1-i]+1for i in range(len(forward_candy)): # fianlif forward_candy[i]>backward_candy[i]: final_candy[i]=forward_candy[i] else:final_candy[i]=backward_candy[i] return sum(final_candy)