Problema
For each number, find the closest earlier position containing a strictly smaller number. Equal numbers do not qualify. Positions start at 1; use 0 when there is no smaller number to the left.
Implement nearest_smaller_value(numbers).
Input
numbers: Numbers in their original order.
Output
Return one earlier position (or 0) for every input value.
Restricciones
0…200,000 integers, each between −1,000,000,000 and 1,000,000,000. Empty input returns an empty list.
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 has no earlier value and 2 has no smaller earlier value. Both 5 and 3 find the value 2 at position 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
Earlier equal values are not strictly smaller. Every answer is 0.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
For each position, you need the closest earlier value that is strictly smaller, not smaller-or-equal.
Pista 2
Maintain a monotonic stack of candidate values with their positions while scanning left to right.
Pista 3
Pop equal or larger values, since they can never be the nearest smaller answer for later elements.
Complejidad esperada
O(n) time, O(n) extra space
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.