Problema
En cada movimiento puedes aumentar en 1 el valor de un elemento del arreglo. Haz que el arreglo sea no decreciente: cada valor debe ser mayor o igual al que está inmediatamente antes. No puedes disminuir valores ni reordenarlos.
Implementa increasing_array(numbers).
Entrada
numbers: Los valores en su orden original.
Salida
Devuelve el número mínimo total de incrementos unitarios.
Restricciones
1 ≤ longitud ≤ 200,000. Cada valor está entre 1 y 1,000,000,000. Usa un resultado con signo de 64 bits.
Ejemplos
Entrada:
numbers = [4, 1, 3]
Salida esperada:
expected = 4Entrada:
std::vector<long long> numbers = {4, 1, 3};
Salida esperada:
long long expected = 4;Entrada:
long[] numbers = new long[] {4, 1, 3};
Salida esperada:
long expected = 4;Explicación
Sube el 1 a 4 usando tres movimientos y el 3 a 4 usando un movimiento. El resultado [4, 4, 4] usa cuatro movimientos.
Entrada:
numbers = [1, 2, 2, 5]
Salida esperada:
expected = 0Entrada:
std::vector<long long> numbers = {1, 2, 2, 5};
Salida esperada:
long long expected = 0;Entrada:
long[] numbers = new long[] {1, 2, 2, 5};
Salida esperada:
long expected = 0;Explicación
Cada valor ya es al menos igual al valor anterior; se permiten valores vecinos iguales.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Recorre de izquierda a derecha, porque cada valor solo depende del anterior.
Pista 2
Cuando un valor sea demasiado pequeño, súbelo solo lo justo para igualar el mínimo acumulado permitido.
Pista 3
Lleva bien la cuenta de los incrementos, porque las subidas anteriores afectan las comparaciones posteriores.
Complejidad esperada
tiempo O(n), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.