题目描述：

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个孩子站成一排。每一个孩子都被赋予一个评分。

你现在为这些孩子分配糖果，需要满足下面的要求：

每一个孩子至少要分得1个糖果。

评分高的孩子得到的糖果要多余他的邻居（左右两边）。

你最少要给出多少个糖果？

解题思路：

贪心算法（Greedy Algorithm）

评分同时低于左右两边的孩子只需分配一个糖果

评分相同的相邻孩子，分配的糖果可以不同

算法步骤如下：

1. 首先为每一个孩子分配1个糖果

记当前孩子序号为i，糖果数为candies[i]，评分为ratings[i]

2. 从左向右遍历，若ratings[i] > ratings[i - 1]，则令candies[i] = candies[i - 1] + 1

3. 从右向左遍历，若ratings[x] > ratings[x + 1]，则令candies[x] = max(candies[x], candies[x + 1] + 1)

Python代码：

class Solution:
    # @param {integer[]} ratings
    # @return {integer}
    def candy(self, ratings):
        size = len(ratings)
        candies = [1] * size
        for x in range(1, size):
            if ratings[x] > ratings[x - 1]:
                candies[x] = candies[x - 1] + 1
        for x in range(size - 2, -1, -1):
            if ratings[x] > ratings[x + 1]:
                candies[x] = max(candies[x], candies[x + 1] + 1)
        return sum(candies)

 

本文链接：http://bookshadow.com/weblog/2015/08/06/leetcode-candy/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码