本文共 1843 字，大约阅读时间需要 6 分钟。

题目要求比其高的邻居要比本身的奖励多，那么最少也要多一个，所有我们可以找到所有的凹点，凹点如下三种情形。

找到所有的凹点后，我们就可以从凹点处开始向左右两个方向依次查找递增序列，其中每个高的都要比相邻的矮的多一个，比如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)