问题分析
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?
问题分析
我想的思路超时了,于是到网上找了解题报告,具体做法为两遍遍历。首先从左向右遍历ratings数组,若本身比左邻居排名高,则将自身candy数设为左邻居值+1;然后从右向左遍历ratings数组,若本身比右邻居排名高,且当前candy没有比右邻居多,则将自身candy数设为右邻居值+1。
AC代码
class Solution(object):
def candy(self, ratings):
"""
:type ratings: List[int]
:rtype: int
"""
n = len(ratings)
if n < 2:
return n
cd = [1 for i in range(n)]
for i in range(1, n):
if ratings[i] > ratings[i-1]:
cd[i] = cd[i-1] + 1
for i in range(n-2, -1, -1):
if ratings[i] > ratings[i+1] and cd[i] < cd[i+1] + 1:
cd[i] = cd[i+1] + 1
return sum(cd)
Runtime: 92 ms, which beats 65.71% of Python submissions.
网友评论