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.
class Solution:
     def candy(self, ratings):
         """
         :type ratings: List[int]
         :rtype: int
         """
         if not ratings: return 0
         if len(ratings) == 1: return 1
         l2r = [1 for _ in ratings]
         r2l = [1 for _ in ratings]
         for i in range(1, len(ratings)):
             if ratings[i] > ratings[i - 1]:
                 l2r[i] = l2r[i - 1] + 1
         for i in range(len(ratings) - 2, -1, -1):
             if ratings[i] > ratings[i + 1]:
                 r2l[i] = r2l[i + 1] + 1
         res = 0
         for i in range(len(ratings)):
             res += max(l2r[i], r2l[i])
         return res
class Solution:
     def candy(self, ratings):
         """
         :type ratings: List[int]
         :rtype: int
         """
         if not ratings: return 0
         if len(ratings) == 1: return 1
         l2r = [1 for _ in ratings]
         r2l = [1 for _ in ratings]
         for i in range(1, len(ratings)):
             if ratings[i] > ratings[i - 1]:
                 l2r[i] = l2r[i - 1] + 1
         for i in range(len(ratings) - 2, -1, -1):
             if ratings[i] > ratings[i + 1]:
                 r2l[i] = r2l[i + 1] + 1
         res = 0
         for i in range(len(ratings)):
             res += max(l2r[i], r2l[i])
         return res