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)