# Untitled

unknown

python

2 years ago

1.3 kB

14

Indexable

Never

^{}

""" There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. 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. Return the minimum number of candies you need to have to distribute the candies to the children. test_cases = [ ([1,0,2], 5), ([1,2,2], 4), ] [2,1,2] => 5 [1,2,1] => 4 child i = 1 left < child i < right cand[i] = max(cand[i-1], cand[i+1]) + 1 """ def solution(ratings): cand = [1 for _ in ratings] sorted_ratings = [[rating, i] for i, rating in enumerate(ratings)] sorted_ratings.sort() for rating, i in sorted_ratings: neighbor_candies = [] if i - 1 >= 0 and ratings[i-1] < rating: # left neighbor neighbor_candies.append(cand[i-1]) if i + 1 < len(ratings) and ratings[i+1] < rating: # right neighbor neighbor_candies.append(cand[i+1]) if neighbor_candies: cand[i] = max(neighbor_candies) + 1 return sum(cand) test_cases = [ ([1,0,2], 5), ([1,2,2], 4), ] for test_case, ans in test_cases: print(solution(test_case) == ans)