The first one is O(n) space, but very concise. The idea is to find the mininum candies for each child considering only left or right neighbors.
class Solution: # @param ratings, a list of integer # @return an integer def candy(self, ratings): candies =  * len(ratings) for i in xrange(len(ratings) - 1): if ratings[i + 1] > ratings[i]: candies[i + 1] = max(candies[i + 1], candies[i] + 1) j = -i - 1 if ratings[j - 1] > ratings[j]: candies[j - 1] = max(candies[j - 1], candies[j] + 1) return sum(candies)
The second one is O(1) space, a little bit more complicated. The idea is during one scan find all up-then-down hills in the ratings.
class Solution: # @param ratings, a list of integer # @return an integer def candy(self, ratings): if len(ratings) == 1: return 1 def count_hill(up, down): x, y = max(up, down), min(up, down) - 1 return (x * (x + 1) + y * (y + 1)) / 2 up = down = extra = 0 direction = ratings - ratings for i in xrange(1, len(ratings)): if direction > 0: up += 1 # one more on the uphill side if direction < 0: down += 1 # one more on the downhill side if i == len(ratings) - 1: break dr = ratings[i + 1] - ratings[i] if dr == 0 or direction < 0 < dr: # count extra for a hill extra += count_hill(up, down) up = down = 0 direction = dr return extra + count_hill(up, down) + len(ratings)
I know it is an old thread but just in case anyone see and understand the second solution:
Could you please explain how the hill counting work?
My vague understanding is that to count a hill, it is essentially calculating the area under it ? (x * (x + 1) + y * (y + 1)) / 2 seems to be the area of two triangles but not very sure about it.