1 | 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. |
- 分治法
将小孩分成两边,分别计算每一边需要最优糖果分配。
在合并时,有两种边界情况需要考虑,这里设mid为二分中点,左边界为mid,右边界为mid+1,最优糖果分配数组为candy:
a) rating[mid] > rating[mid+1] and candy[mid] < candy[mid+1]
此时左边界违背了题中条件,需要调整左边界rating值为右边界值+1,并接着调整左边小孩的值。
b) rating[mid] < rating[mid+1] and candy[mid] > candy[mid+1]
此时右边界违背了题中条件,需要调整右边界rating值为左边界+1,并接着调整右边小孩的值。
具体代码如下:1
def candyUtil(ratings, left, right, candies):
if left == right:
candies[left] = 1
return 1
mid = (left+right) / 2
leftCandy = candyUtil(ratings, left, mid, candies)
rightCandy = candyUtil(ratings, mid+1, right, candies)
if ratings[mid] < ratings[mid+1]:
if candies[mid] >= candies[mid+1]:
j = mid+1
while j <= right and ratings[j] > ratings[j-1] and candies[j] <= candies[j-1]:
rightCandy += candies[j-1]+1-candies[j]
candies[j] = candies[j-1]+1
j += 1
elif ratings[mid] > ratings[mid+1]:
if candies[mid] <= candies[mid+1]:
j = mid
while j >= 0 and ratings[j] > ratings[j+1] and candies[j] <= candies[j+1]:
leftCandy += candies[j+1]+1-candies[j]
candies[j] = candies[j+1]+1
j -= 1
print left, right, candies
return leftCandy+rightCandy
def candyDivide(ratings):
return candyUtil(a, 0, len(a)-1, [1]*len(ratings))
递推公式为T(n) = 2T(n/2) + O(n)
时间复杂度为O(n),空间复杂度为O(n)
- 贪心算法
采用类似贪心思想,扫描数组两次。
第一次从左往右扫描,当rating[i] > rating[i-1]时,candy[i] = candy[i-1]+1
保证如果第i个孩子的rating值如果大于其左边i-1孩子的值,那么它分得的糖果一定比左边的多。
第二次从右往左扫描,,当rating[i] > rating[i+1]时,candy[i] = max(candy[i], candy[i+1]+1)
保证第i个孩子的rating值如果大于其右边i+1孩子的值,那么他分得的糖果一定比右边孩子多。
两次扫描,分别保证了孩子左边和右边情况,并且一定是最优的。1
def candy(self, ratings):
ret = 0
c = [1] * len(ratings)
for i in range(1, len(ratings)):
if ratings[i] > ratings[i-1]:
c[i] = c[i-1]+1
else:
c[i] = 1
ret = c[-1]
for i in reversed(range(len(c)-1)):
if ratings[i] > ratings[i+1]:
c[i] = max(c[i+1]+1, c[i])
ret += c[i]
return ret
时间复杂度为O(n),空间复杂度为O(n)