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

题意：每个小朋友有一个rating值， 为每个小朋友分配糖果，如果某个小朋友的rating比相邻的某个人高，则他的糖果也要比他多。问最少需要给出去多少糖果

题解：这是一个贪心，先正着扫一边，如果序列递增，则糖果数依次加一，如果遇到变小的则设为1。 得到最少的糖果序列 。

           然后再反向贪心一遍。 最后把两个序列求max  然后相加即可

>.< 很久没做过算法一直在做水题。 就当学python了吧。  

class Solution:    # @param {integer[]} ratings    # @return {integer}    def candy(self, ratings):        num = [1]         cnt = 1         for i in range(1,len(ratings)) :            if ratings[i]>ratings[i-1] :                cnt += 1            else :                cnt = 1             num.append(cnt)       # ans = num.pop()        ans = num[len(ratings)-1]        cnt = 1         for i in range(len(ratings)-1,0,-1) :            if ratings[i-1]>ratings[i] :                cnt += 1            else :                cnt = 1             ans += max ( num[i-1], cnt )        return ans if __name__ == '__main__' :    a = Solution ()    ratings = [1,2,3,4,3,2,1]    ans2 = a.candy(ratings)    print ans2~                                                                                                           ~

转载地址：http://linpi.baihongyu.com/