one loop python solution


  • 0
    R

    just think descending case:
    (make that last of descending children get 1 candy)
    1,2,10,8,7,5,4,3 in this example,i will give 3 candies to rating-10,then find the last index of descending(last one),so from rating-8 to rating-3 the candies should be 5,4,3,2,1,so after that plus diff between rating-10 and rating-8 on rating-10(3+(5 - 3)+1) to make sure that rating-10 greater than rating-8

    1,2,10,6,4 in this example is much easier,3 candies to rating-10,then iterate descending,rest candies should be 2,1, it demands requirements

    class Solution(object):
        def candy(self, ratings):
            """
            :type ratings: List[int]
            :rtype: int
            """
            sum_candy=1    #total
            give_candy=1    #every step candy
            i=1
            while i<len(ratings):
                if ratings[i]==ratings[i-1]:
                    give_candy=1                #rating same but candy diff
                    sum_candy+=give_candy
                    i+=1
                elif ratings[i] > ratings[i-1]:
                    give_candy+=1
                    sum_candy+=give_candy
                    i+=1
                else:                                 #just consider descending
                    j=i-1
                    last_peak=give_candy
                    while i<len(ratings) and ratings[i]<ratings[i-1]:
                        i+=1
                    if give_candy-(i-j-1)>0:    #last peak is enougth big to greater than next
                        for x in range(j+1,i):
                            give_candy=i-x
                            sum_candy+=give_candy
                    else:                       #last peak not enougth to greater than next
                        for x in range(j+1,i):
                            give_candy=i-x
                            sum_candy+=give_candy
                        sum_candy+=abs(last_peak-(i-j-1))+1 #add diff to last peak
            return sum_candy
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.