难度: Hard
原题连接
内容描述
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 - 时间复杂度: O(N)- 空间复杂度: O(N)******
- 首先我们从左往右边看，如果当前child的rating比它左边child的rating大，那么当前child分的candy肯定要比它左边多1
- 然后从右往左边看，如果当前child的rating比它右边child的rating大，那么当前child分的candy肯定要比它右边多1
我们知道这两种情况我们都必须满足，所以最后我们取两者中的大者（这样才能同时满足两种情况）,beats 24.83%
class Solution:
def candy(self, ratings):
"""
:type ratings: List[int]
:rtype: int
"""
left2right = [1] * len(ratings)
right2left = [1] * len(ratings)
for i in range(1, len(ratings)):
if ratings[i] > ratings[i-1]:
left2right[i] = left2right[i-1] + 1
for i in range(len(ratings)-2, -1, -1):
if ratings[i] > ratings[i+1]:
right2left[i] = right2left[i+1] + 1
res = 0
for i in range(len(ratings)):
res += max(left2right[i], right2left[i])
return res思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******
刚才用了2个array，其实我们可以只用一个array， beats 28.77%
class Solution:
def candy(self, ratings):
"""
:type ratings: List[int]
:rtype: int
"""
res = [1] * len(ratings) # also compatable with [] input
# left scan
for i in range(1, len(ratings)):
if ratings[i] > ratings[i-1]:
res[i] = res[i-1] + 1
# right scan
for i in range(len(ratings)-2, -1, -1):
if ratings[i] > ratings[i+1]:
res[i] = max(res[i+1]+1, res[i])
return sum(res)思路 3 - 时间复杂度: O(N)- 空间复杂度: O(1)******
其实我们还有另外一种思路，可以将空间降到O(1)
假设：
input: [2, 4, 6, 8, 7, 6, 5, 4, 3, 2, 7, 8, 9, 8, 7, 6, 5, 4, 3]
child index: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14,15,16,17,18,19]
我们先直接给第一个孩子1颗candy，然后继续往下遍历，我们发现第2个孩子的rating比第一个孩子的多，于是我们给第二个孩子2颗candy， 以此类推，第3个孩子3颗candy，第4个孩子4颗candy，这时候我们发现第5个孩子的rating比第4个孩子的rating要小， 所以第5个孩子的candy肯定要比第4个孩子的少才行，但是不能直接给第5个孩子1颗candy这么简单，因为说不定后面孩子的rating比第5个孩子更小呢？ 如果第5个孩子只有1颗candy，后面的孩子岂不是没有candy了？这不符合题目要求，所以我们暂时继续走下去，我们发现一共降序走了6步，此时来到了第11个孩子， rating终于又变成升序了，这时候我们知道了，第5个孩子最少需要给6颗candy了，然后第6，7，8，9，10个孩子依次给5，4，3，2，1颗candy，总数就是6*(1+6)/2 但是问题来了，第5个孩子给了6颗candy，第4个孩子应该要比第5个孩子的candy更多呀， 于是我们补给第4个孩子3颗candy，此时第4个孩子有7颗candy （比第5个孩子的6颗多，符合题目要求）。继续走下去，第11个孩子给2颗candy，第12个孩子给3颗candy，第13个孩子给4颗candy，接下来又是降序了， 又是降序走了6步，一样的原理，第14,15,16,17,18,19个孩子分别给6,5,4,3,2,1颗candy，发现第13个孩子需要补3颗candy（现在7颗candy）
于是我们的candy的总和为
input: [2, 4, 6, 8, 7, 6, 5, 4, 3, 2, 7, 8, 9, 8, 7, 6, 5, 4, 3]
child candy: [1, 2, 3, 7, 6, 5, 4, 3, 2, 1, 2, 3, 7, 6, 5, 4, 3, 2, 1]
child index: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14,15,16,17,18,19]
一共67颗candy
编码实现, beats 59.40%
class Solution:
def candy(self, ratings):
"""
:type ratings: List[int]
:rtype: int
"""
if not ratings:
return 0
res, prev, desc_cnt = 1, 1, 0
for i in range(1, len(ratings)):
if ratings[i] >= ratings[i-1]:
if desc_cnt > 0:
res += desc_cnt * (desc_cnt + 1) / 2 # arithmetic progression
if desc_cnt >= prev:
res += desc_cnt - prev + 1
desc_cnt = 0
prev = 1
# 当前child的rating和它左边child的rating一样，直接给1颗candy就满足了，否则需要给prev+1颗candy
prev = 1 if ratings[i] == ratings[i-1] else prev + 1
res += prev
else:
desc_cnt += 1
if desc_cnt > 0: # if we were descending at the end
res += desc_cnt * (desc_cnt + 1) / 2 # arithmetic progression
if desc_cnt >= prev:
res += desc_cnt - prev + 1
return int(res)