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.
Restrições
0…200,000 integers, each between −1,000,000,000 and 1,000,000,000. Empty input returns an empty list.
Exemplos
Entrada:
numbers = [4, 2, 5, 3]
Saída esperada:
expected = [0, 0, 2, 2]Entrada:
std::vector<long long> numbers = {4, 2, 5, 3};
Saída esperada:
std::vector<long long> expected = {0, 0, 2, 2};Entrada:
long[] numbers = new long[] {4, 2, 5, 3};
Saída esperada:
long[] expected = new long[] {0, 0, 2, 2};Explicação
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]
Saída esperada:
expected = [0, 0, 0]Entrada:
std::vector<long long> numbers = {2, 2, 2};
Saída esperada:
std::vector<long long> expected = {0, 0, 0};Entrada:
long[] numbers = new long[] {2, 2, 2};
Saída esperada:
long[] expected = new long[] {0, 0, 0};Explicação
Earlier equal values are not strictly smaller. Every answer is 0.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Para cada posição, você precisa do valor anterior mais próximo que seja estritamente menor, não menor ou igual.
Dica 2
Mantenha uma pilha monotônica de candidatos com suas posições enquanto percorre da esquerda para a direita.
Dica 3
Remova valores iguais ou maiores, pois eles nunca serão a resposta mais próxima para elementos futuros.
Complexidade esperada
tempo O(n), espaço extra O(n)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.