Problème
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.
Contraintes
0…200,000 integers, each between −1,000,000,000 and 1,000,000,000. Empty input returns an empty list.
Exemples
Entrée :
numbers = [4, 2, 5, 3]
Sortie attendue :
expected = [0, 0, 2, 2]Entrée :
std::vector<long long> numbers = {4, 2, 5, 3};
Sortie attendue :
std::vector<long long> expected = {0, 0, 2, 2};Entrée :
long[] numbers = new long[] {4, 2, 5, 3};
Sortie attendue :
long[] expected = new long[] {0, 0, 2, 2};Explication
4 has no earlier value and 2 has no smaller earlier value. Both 5 and 3 find the value 2 at position 2.
Entrée :
numbers = [2, 2, 2]
Sortie attendue :
expected = [0, 0, 0]Entrée :
std::vector<long long> numbers = {2, 2, 2};
Sortie attendue :
std::vector<long long> expected = {0, 0, 0};Entrée :
long[] numbers = new long[] {2, 2, 2};
Sortie attendue :
long[] expected = new long[] {0, 0, 0};Explication
Earlier equal values are not strictly smaller. Every answer is 0.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Pour chaque position, vous avez besoin de la valeur précédente la plus proche qui soit strictement plus petite, pas plus petite ou égale.
Indice 2
Maintenez une pile monotone de candidats avec leurs positions en parcourant de gauche à droite.
Indice 3
Retirez les valeurs égales ou plus grandes, car elles ne pourront jamais être la réponse la plus proche pour les éléments suivants.
Complexité attendue
temps O(n), espace supplémentaire O(n)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.