题目要求的比它的邻居比自己奖励，因此，我们有最少一个多的。所有我们可以找到所有的坑，凹坑例如，存在以下三种情况。

找到全部的凹点后，我们就能够从凹点处開始向左右两个方向依次查找递增序列。当中每一个高的都要比相邻的矮的多一个。比方1,2,5,4.我们找到凹点为1 和4，那么从1開始向左没有其它点，我们向右，依次得到2 比1高，2的糖果应该是1的基础上加1。为2， 5比2高，5的糖果是在2的基础上加1，为3。

令一个凹点4， 向左，5比4高，5的糖果应该是在4的基础上加 1，为2，这时我们发现冲突了，从凹点1 開始，我们得到的5的糖果是3。可是从凹点 4 開始，我们得到的糖果数却为2 ，此时我们选择哪个呢？当然，假设要少的，当然是2，可是它却违反了题目中的限定条件。5假设为2 ，就不比2的糖果数多了，所以这时我们就应该选择最大的，这说明了什么呢？说明从左面開始向右到 5 得到的递增序列的长度大于从4開始向左到5得到的递增序列。

也就是说，得到的糖果数的多少，取决于所构成的连续递增序列的长度。

class Solution:	def candy(self, A):		if len(A) == 0: return 0		candies = [1] * len(A)		#insert two guard at both bounder		#为了便于处理凹点，我们在左右边界各插入一个点作为哨兵，这样在比較的时候		#就不用额外处理边界点了。

A.insert(0, A[0]) A.append(A[-1]) #pits 用来存储全部的凹点下标 pits = [] for i in range(1, len(A) - 1): if A[i] <= A[i - 1] and A[i] < A[i + 1] or \ A[i] <= A[i + 1] and A[i] < A[i - 1]: pits.append(i) #从左到右一次处理各个凹点 for i in pits: # go left j = i while A[j - 1] > A[j]: #由于A数组增加了哨兵的缘故，所以A和candies的下标不是严格对齐的，差了一个 if candies[j - 2] < candies[j - 1] + 1: candies[j - 2] = candies[j - 1] + 1 j -= 1 else: break # go right j = i while A[j + 1] > A[j]: if candies[j] < candies[j - 1] + 1: candies[j] = candies[j - 1] + 1 j += 1 else: break return sum(candies)

这里我们须要一个额外的pits数组来存储全部的凹点，事实上通过刚才我们的分析，第二种实现方式已经出现了，就是从左開始，找递增序列，然后添加糖果。对于每一个数，它和左边构成的递增序列与从右面构成的递增序列可能不一样，如上例中的5，跟左边够成的递增序列为 1,2 5，长度为3，跟右面的构成的递增序列为4,5，长度为2，而5最少的糖果数是取决于最长的递增序列的。所以我们就能够从左到右遍历一遍。然后再从右向左遍历一遍。取两次遍历的最大值。

class Solution:	def candy(self, A):		if len(A) == 0: return 0		candies = [1] * len(A)		#从左向右，按着递增来分配糖果		for i in range(1, len(A)):		    if A[i] > A[i - 1]:		        candies[i] = candies[i - 1] + 1		        		#从右向左，按着递增来分配糖果。并取最大值		for i in xrange(len(A) - 2, -1, -1):		    if A[i] > A[i + 1] and candies[i] < candies[i + 1] + 1:		        candies[i] = candies[i + 1] + 1		        		return sum(candies)

版权声明：本文博客原创文章，博客，未经同意，不得转载。