描述
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?
分析
有一定难度。对于某个位置i
上的小孩,它的糖果数取决于他自己和左右邻居的关系。设ratings
数组为R
,分配给小孩的糖果数为数组C
。我们可以这样来考虑这个问题,拆分为两个步骤:
- 首先,如果只要求
C[i] > C[i-1]
iffR[i] > R[i-1]
,也就是说只考虑每个小孩左手边的小孩,那么如果R[i] > R[i-1]
则C[i] = C[i-1] + 1
,否则C[i] = 1
。 - 然后我们再考虑加上右手边小孩的限制,如果
R[i] > R[i+1]
,则C[i] = max(C[i+1] + 1, C[i])
。
这样一来,考虑到上面被分解的两个问题内部的互相依赖情况,我们就可以用两个循环分别从左到右、从右到左遍历数组,得到时间O(n)
,空间O(n)
的算法。
代码
Python
1 | class Solution(object): |