Question: https://oj.leetcode.com/problems/candy/
Question Name: Candy
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | class Solution: # @param ratings, a list of integer # @return an integer def candy(self, ratings): sortedRatings = enumerate(ratings) sortedRatings = sorted(sortedRatings, key = lambda x: x[1]) candyCount = [-1] * len(ratings) # Lowest rating, First service. for child in sortedRatings: position = child[0] # Each child must have at least one candy. candyForThisChild = 1 # Children with a higher rating get more candies than their # neighbors. # Check its left neighbor, if exists. if position != 0 and ratings[position-1] < ratings[position]: candyForThisChild = max(candyForThisChild, candyCount[position-1] + 1) # Check its right neighbor, if exists. if position != len(ratings)-1 and ratings[position+1] < ratings[position]: candyForThisChild = max(candyForThisChild, candyCount[position+1] + 1) candyCount[position] = candyForThisChild return sum(candyCount) |