Menor início para um percurso positivo
A missão
Problema
Você escolhe um número inteiro positivo como valor inicial e depois soma a ele os números de uma lista, um de cada vez, da esquerda para a direita. Retorne o menor valor inicial para o qual a soma acumulada nunca fica abaixo de 1 em nenhum passo.
Exemplos
Input: nums = [-3, 2, -3, 4, 2]
Output: 5
Por quê: 5 passa por 2, 4, 1, 5, 7, enquanto 4 chegaria a 0 depois do terceiro passo
Input: nums = [1, 2]
Output: 1
Por quê: o total só cresce, então o menor início positivo funciona
Input: nums = [1, -2, -3]
Output: 5
Por quê: edge case: o ponto mais baixo vem bem no final
Dicas
0 / 3
Testar os valores iniciais um a um funciona, mas repete o percurso inteiro a cada vez. Que único fato sobre a lista decide a resposta?
O início é somado a cada soma acumulada, então só a menor soma acumulada importa. Ela precisa ser elevada a pelo menos 1.
Percorra a lista uma vez, guardando a soma acumulada e o menor valor que ela atingiu, começando de 0 para que o momento antes de qualquer passo também conte. A resposta é 1 menos esse menor valor.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Solução
É o tanque de combustível da aula do posto de gasolina: a soma acumulada é o tanque, e o valor inicial é o combustível que você leva junto. Somar um valor inicial s eleva cada soma acumulada em exatamente s, então o percurso fica em 1 ou acima exatamente quando s mais a menor soma acumulada é pelo menos 1. Uma passada encontra esse menor total. Começar o mínimo em 0 cobre as listas cuja soma acumulada nunca fica negativa, em que a resposta é o menor início positivo, 1. O tempo é O(n) e o espaço é 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])) # -> 5Travou na ideia, e não no código? Gas Station explica isso.