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?

Example 1:


Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.


Example 2:


Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Greedy algorithms

Starter code: class Solution:
    def candy(self, ratings: List[int]) -> int:
        

Solutions:
class Solution:

	def candy(self, ratings):
		if not ratings:
			return 0
		(total, pre, decrease) = (1, 1, 0)
		for i in range(1, len(ratings)):
			if ratings[i] >= ratings[i - 1]:
				if decrease > 0:
					total += (1 + decrease) * decrease // 2
					if pre <= decrease:
						total += decrease + 1 - pre
					(decrease, pre) = (0, 1)
				if ratings[i] == ratings[i - 1]:
					total += 1
					pre = 1
				else:
					pre += 1
					total += pre
			else:
				decrease += 1
		if decrease > 0:
			total += (1 + decrease) * decrease // 2
			if pre <= decrease:
				total += decrease + 1 - pre
		return total


class Solution:

	def candy(self, ratings):
		current_min = 1
		current_max = 1
		desc_len = 1
		cnt = 1
		for i in range(1, len(ratings)):
			if ratings[i] < ratings[i - 1]:
				if current_min == 1:
					if desc_len >= current_max:
						cnt += desc_len + 1
					else:
						cnt += desc_len
				else:
					current_max = current_min
					current_min = 1
					cnt += 1
				desc_len += 1
			elif ratings[i] > ratings[i - 1]:
				current_min += 1
				current_max = current_min
				cnt += current_min
				desc_len = 1
			else:
				cnt += 1
				current_min = 1
				current_max = 1
				desc_len = 1
		return cnt


class Solution:

	def candy(self, ratings):
		n = len(ratings)
		result = [1] * n
		for i in range(n - 1):
			if ratings[i + 1] > ratings[i]:
				result[i + 1] = result[i] + 1
		for i in range(n - 1, 0, -1):
			if ratings[i - 1] > ratings[i]:
				result[i - 1] = max(result[i] + 1, result[i - 1])
		return sum(result)


class Solution:

	def candy(self, ratings):
		candy = [1 for i in range(len(ratings))]
		for i in range(1, len(ratings)):
			if ratings[i] > ratings[i - 1]:
				candy[i] = candy[i - 1] + 1
		for i in range(len(ratings) - 1)[::-1]:
			if ratings[i] > ratings[i + 1]:
				candy[i] = max(candy[i], candy[i + 1] + 1)
		return sum(candy)


class Solution:

	def candy(self, ratings):
		if not ratings:
			return 0
		if len(ratings) == 1:
			return 1
		l2r = [1 for _ in ratings]
		for i in range(1, len(ratings)):
			if ratings[i] > ratings[i - 1]:
				l2r[i] = l2r[i - 1] + 1
		res = l2r[-1]
		for i in range(len(ratings) - 2, -1, -1):
			if ratings[i] > ratings[i + 1]:
				l2r[i] = max(l2r[i], l2r[i + 1] + 1)
			res += l2r[i]
		return res


class Solution:

	def candy(self, ratings):
		candies = [0] * len(ratings)
		from_left = [1] * len(ratings)
		cur_less_than = 1
		for idx in range(1, len(ratings)):
			if ratings[idx - 1] < ratings[idx]:
				cur_less_than += 1
			else:
				cur_less_than = 1
			from_left[idx] = cur_less_than
		from_right = [1] * len(ratings)
		cur_less_than = 1
		idx = len(ratings) - 2
		while idx >= 0:
			if ratings[idx + 1] < ratings[idx]:
				cur_less_than += 1
			else:
				cur_less_than = 1
			from_right[idx] = cur_less_than
			idx -= 1
		for idx in range(0, len(ratings)):
			candies[idx] = max(from_left[idx], from_right[idx])
		return sum(candies)