leetcode135-- 分糖问题

# 小郑之家~

### 题目

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?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.



### 解法1

class Solution(object):
def candy(self, ratings):
"""
:type ratings: List[int]
:rtype: int
"""
res = 0
n = len(ratings)
nums = [1]*n

# 第一次遍历，如果右边的权要大的话，就让他的比左边的多一个
for i in range(n-1):
if ratings[i+1] > ratings[i]:
nums[i+1] = nums[i]+1

# 第二次遍历，如果左边的比较高的话，这时候要看需不需要给他加了
for i in range(n-1, 0, -1):
if ratings[i-1] > ratings[i]:
nums[i-1] = max(nums[i-1], nums[i]+1)

return sum(nums)