Menor inicio para un recorrido positivo
La misión
Problema
Eliges un número entero positivo como valor inicial y luego le sumas los números de una lista uno por uno, de izquierda a derecha. Devuelve el menor valor inicial con el que el total acumulado nunca baja de 1 en ningún paso.
Ejemplos
Input: nums = [-3, 2, -3, 4, 2]
Output: 5
Por qué: 5 pasa por 2, 4, 1, 5, 7, mientras que 4 llegaría a 0 después del tercer paso
Input: nums = [1, 2]
Output: 1
Por qué: el total solo crece, así que funciona el menor inicio positivo
Input: nums = [1, -2, -3]
Output: 5
Por qué: caso límite: el punto más bajo llega justo al final
Pistas
0 / 3
Probar valores iniciales uno por uno funciona, pero repite todo el recorrido cada vez. ¿Qué único dato de la lista decide la respuesta?
El inicio se suma a cada total acumulado, así que solo importa el total acumulado más bajo. Hay que subirlo hasta al menos 1.
Recorre la lista una vez llevando la suma acumulada y el valor más bajo que alcanzó, empezando desde 0 para que también cuente el momento antes de cualquier paso. La respuesta es 1 menos ese valor más bajo.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Solución
Es el tanque de combustible de la lección Gas Station: la suma acumulada es el tanque, y un valor inicial es el combustible que traes contigo. Sumar un valor inicial s sube cada total acumulado exactamente en s, así que el recorrido se mantiene en 1 o más justo cuando s más el total acumulado más bajo es al menos 1. Una pasada encuentra ese total más bajo. Empezar el mínimo en 0 cubre las listas cuya suma acumulada nunca se vuelve negativa, donde la respuesta es el menor inicio positivo, 1. El tiempo es O(n) y el espacio es O(1).
def smallest_start(nums):
total = lowest = 0
for x in nums:
total += x
lowest = min(lowest, total) # the deepest dip of the running sum
return 1 - lowest # lowest <= 0, so this is at least 1
print(smallest_start([-3, 2, -3, 4, 2])) # -> 5
print(smallest_start([1, 2])) # -> 1
print(smallest_start([1, -2, -3])) # -> 5¿Lo que te frena es la idea y no el código? Gas Station lo explica.