Leetcode: Candy


Similar Problems:

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?

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/candy
## Basic Ideas:
##   Assign each child 1 candy
##   From left to right, if the latter one has a bigger value, change the latter value
##   From right to left, if the former one has a bigger value, change the former value
##   Collect the result
##   Assumption: if the same rating, they don't have to get the same amount of candies
## Complexity: Time O(n), Space O(n)
class Solution:
    def candy(self, ratings):
        :type ratings: List[int]
        :rtype: int
        length = len(ratings)
        l = [1] * length
        for i in range(length-1):
            if ratings[i+1] > ratings[i]: l[i+1] = l[i]+1

        for i in range(length-1, 0, -1):
            if ratings[i-1] > ratings[i] and l[i-1]<=l[i]:
                l[i-1] = l[i]+1

        return sum(l)

Share It, If You Like It.

Leave a Reply

Your email address will not be published.