Dulces

Hay n niños haciendo una fila. Cada niño tiene una calificación según el arreglo de enteros ratings.

Le das dulces a estos niños según los siguientes requisitos:

  • Cada niño debe tener al menos un dulce.
  • Los niños con una calificación más alta obtienen más dulces que sus vecinos.

Devuelve el número mínimo de dulces que necesitas tener para distribuir los dulces a los niños.

Ejemplos

Ejemplo 1:

Input: ratings = [1,0,2] Output: 5 Explicación: Puedes asignar al primer, segundo y tercer niño con 2, 1, 2 dulces respectivamente.

Ejemplo 2:

Input: ratings = [1,2,2] Output: 4 Explicación: Puedes asignar al primer, segundo y tercer niño con 1, 2, 1 dulces respectivamente. El tercer niño obtiene 1 dulce porque satisface las dos condiciones anteriores.

Soluciones

Python
class Solution:
   def candy(self, ratings: List[int]) -> int:
       n = len(ratings)
       candies = [1] * n
       
       # Paso 1: Asignar curva creciente con dulces crecientes
       for i in range(1, n):
           if ratings[i] > ratings[i-1]:
               candies[i] = 1 + candies[i-1]
       
       # Paso 2: Asignar curva decreciente con dulces crecientes
       total = candies[-1]
       for i in range(n-1, 0, -1):
           if ratings[i-1] > ratings[i]:
               candies[i-1] = max(candies[i-1], 1 + candies[i])
           total += candies[i-1]
       
       return total
BUSCARCtrl K