Problema
Para cada número, encuentra la posición anterior más cercana que contenga un número estrictamente menor. Los números iguales no califican. Las posiciones comienzan en 1; usa 0 cuando no haya un número menor a la izquierda.
Implementa nearest_smaller_value(numbers).
Entrada
numbers: Números en su orden original.
Salida
Devuelve una posición anterior (o 0) para cada valor de entrada.
Restricciones
0…200,000 enteros, cada uno entre −1,000,000,000 y 1,000,000,000. Una entrada vacía devuelve una lista vacía.
Ejemplos
Entrada:
numbers = [4, 2, 5, 3]
Salida esperada:
expected = [0, 0, 2, 2]Entrada:
std::vector<long long> numbers = {4, 2, 5, 3};
Salida esperada:
std::vector<long long> expected = {0, 0, 2, 2};Entrada:
long[] numbers = new long[] {4, 2, 5, 3};
Salida esperada:
long[] expected = new long[] {0, 0, 2, 2};Explicación
4 no tiene ningún valor anterior y 2 no tiene ningún valor menor a la izquierda. Tanto 5 como 3 encuentran el valor 2 en la posición 2.
Entrada:
numbers = [2, 2, 2]
Salida esperada:
expected = [0, 0, 0]Entrada:
std::vector<long long> numbers = {2, 2, 2};
Salida esperada:
std::vector<long long> expected = {0, 0, 0};Entrada:
long[] numbers = new long[] {2, 2, 2};
Salida esperada:
long[] expected = new long[] {0, 0, 0};Explicación
Los valores anteriores iguales no son estrictamente menores. Todas las respuestas son 0.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Para cada posición, necesitas el valor anterior más cercano que sea estrictamente menor, no menor o igual.
Pista 2
Mantén una pila monótona de candidatos con sus posiciones mientras recorres de izquierda a derecha.
Pista 3
Saca los valores iguales o mayores, porque nunca pueden ser la respuesta de menor cercano para elementos posteriores.
Complejidad esperada
tiempo O(n), espacio extra O(n)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.