## 题目描述：

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?

## 解题思路：

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

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)
``````

Pingbacks已关闭。

1. Fivezh 发布于 2016年3月25日 21:32 #

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

2. 在线疯狂 发布于 2016年3月26日 09:37 #

感谢更正，已经修改！ :D