candy

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.

1. 分治法

将小孩分成两边，分别计算每一边需要最优糖果分配。
在合并时，有两种边界情况需要考虑，这里设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，并接着调整右边小孩的值。

具体代码如下：

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)

1. 贪心算法

采用类似贪心思想，扫描数组两次。
第一次从左往右扫描，当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孩子的值，那么他分得的糖果一定比右边孩子多。

两次扫描，分别保证了孩子左边和右边情况，并且一定是最优的。

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)