Leetcode-135的解题过程。

• 题目

  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?

• 解析

  给排成一排的N个小朋友们发糖。每个小朋友至少需要分到一块糖，且分数更高的小朋友需要分到比相邻的小朋友更多的糖，求所需的最少糖数。这道题虽然号称Hard，但是个人感觉实际上顶多是Medium的水准，没有太多考验智商的环节。
  首先来看一下预先定义好的参数和返回值：

  1 2 3 4 5

  def candy(self, ratings): """ :type ratings: List[int] :rtype: int """

  显然，输入是列表形式的小朋友分数，输出是最后所需的糖果数。很自然地，首先想到的方法就是贪心法，即首先给每个小朋友分配1个糖果，然后根据情况和限定条件逐个增加糖果，直至满足条件为止。在这道题中，限制条件就是“分数更高的小朋友需要分到比相邻的小朋友更多的糖”，所以当整个序列中的某一处不满足这个条件时，就要给这个分数更高的小朋友加1颗糖果。
  但是单纯地遍历整个序列一次并按照上面的规则加糖显然是不可行的，因为加糖这个操作本身有可能使得附近的位置不再满足条件。例如，如果ratings是以下值：

  1	[5,4,3,2,1]

  那么首先应该给0号小朋友加一颗糖果，随即是1号小朋友。但是1号小朋友拿到2颗糖果后，0号小朋友的要求就不再被满足了。
  那么遍历多次，知道整个序列都满足条件为止呢？理论上这样做是可行的，但是消耗的时间太多，所以我们需要考虑其他的方法。
  从上面的探索中我们可以发现，之所以单次遍历不可行，根本的原因在于，当前小朋友和其左侧的小朋友都要执行加糖，由于当前小朋友在后，才会导致左侧小朋友的要求不满足。也就是说，如果加糖的顺序是从分数从低到高的话，就不会产生这种问题。例如，ratings是以下值时：

  1	[1,2,3,4,5]

  那么很显然，这时一次遍历就可以满足所有小朋友的要求。于是我们可以想到，只要按照分数升序依次为小朋友加糖，就可以得到正确的答案。
  至此，这道题的核心问题已经解决了，此外就是注意边界情况的考虑。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

  class Solution(object): def candy(self, ratings): """ :type ratings: List[int] :rtype: int """ l = len(ratings) if l==1: return 1 i = 0 indices = [] candies = [] for r in ratings: indices.append((r,i)) i+=1 candies.append(1) indices.sort() for ri in indices: rate = ri[0] index = ri[1] if index == 0: if ratings[index]>ratings[index+1] and candies[index]<=candies[index+1]: candies[index] = candies[index+1]+1 elif index == l-1: if ratings[index]>ratings[index-1] and candies[index]<=candies[index-1]: candies[index] = candies[index-1]+1 else: if ratings[index] > ratings[index + 1] and candies[index] <= candies[index + 1]: candies[index] = candies[index + 1] + 1 if ratings[index] > ratings[index - 1] and candies[index] <= candies[index - 1]: candies[index] = candies[index - 1] + 1 return sum(candies)