Description
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.
描述
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1:
输入: [1,0,2] 输出: 5 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:
输入: [1,2,2] 输出: 4 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
思路
- 题意要求满足两个条件：1. 每个孩子都有糖果。2. 得分高的孩子比左右的孩子糖果多。
- 我们用一个数组res表示每个孩子分配得到的糖果，我们初始化每个位置都为1.
- 我们正向遍历数组，如果当前的孩子得分比前一个高，我们就把前面一个孩子分的糖果数加一分给当前孩子。这样一趟遍历完成之后，就满足了得分高的孩子比前面一个孩子分得的糖果多.
- 接下来我们反向遍历，如果当前孩子比后一个孩子评分高，并且当前孩子分的的糖果数小于等于后面一个孩子（如果已经大于了就什么也不用做），我们把后面孩子分得的糖果数加一分给当前孩子。这样结束后，我们就满足了分高的孩子比后面一个孩子糖果多.
- 这样正反遍历完成之后我们就满足的题中的条件，我们再返回糖果的和即可.
# -*- coding: utf-8 -*- # @Author: 何睿 # @Create Date: 2019-01-08 09:48:07 # @Last Modified by: 何睿 # @Last Modified time: 2019-01-09 16:37:40 class Solution: def candy(self, ratings): """ :type ratings: List[int] :rtype: int """ children = len(ratings) # 首先给每一个孩子分一颗糖果 res = [1 for _ in range(children)] # 然后正向遍历，如果当前孩子的评分大于前面一个孩子的评分，则把前一个孩子分的糖果数目加一分给当前孩子 # 这样就满足了每个分高的孩子的糖果大于前一个孩子的糖果 for i in range(1, children): if ratings[i] > ratings[i-1]: res[i] = res[i-1]+1 # 然后反向遍历，如果当前孩子评分比后面一个孩子高，并且档当前孩子已经分得的糖不多有后面一个孩子 # 我们给当前孩子分其后面一个孩子糖果加一个数的糖 for i in range(children-2, -1, -1): if ratings[i] > ratings[i+1] and res[i] <= res[i+1]: res[i] = res[i+1]+1 # 最后我们返回其总和即可 return sum(res)
源代码文件在这里.
