Problem
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.
Einschränkungen
0…200,000 integers, each between −1,000,000,000 and 1,000,000,000. Empty input returns an empty list.
Beispiele
Eingabe:
numbers = [4, 2, 5, 3]
Erwartete Ausgabe:
expected = [0, 0, 2, 2]Eingabe:
std::vector<long long> numbers = {4, 2, 5, 3};
Erwartete Ausgabe:
std::vector<long long> expected = {0, 0, 2, 2};Eingabe:
long[] numbers = new long[] {4, 2, 5, 3};
Erwartete Ausgabe:
long[] expected = new long[] {0, 0, 2, 2};Erläuterung
4 has no earlier value and 2 has no smaller earlier value. Both 5 and 3 find the value 2 at position 2.
Eingabe:
numbers = [2, 2, 2]
Erwartete Ausgabe:
expected = [0, 0, 0]Eingabe:
std::vector<long long> numbers = {2, 2, 2};
Erwartete Ausgabe:
std::vector<long long> expected = {0, 0, 0};Eingabe:
long[] numbers = new long[] {2, 2, 2};
Erwartete Ausgabe:
long[] expected = new long[] {0, 0, 0};Erläuterung
Earlier equal values are not strictly smaller. Every answer is 0.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Für jede Position brauchst du den nächsten früheren Wert, der strikt kleiner ist, nicht kleiner-oder-gleich.
Hinweis 2
Halte beim Scan von links nach rechts einen monotonen Stack mit Kandidatenwerten und ihren Positionen.
Hinweis 3
Entferne gleich große oder größere Werte, denn sie können für spätere Elemente nie die nächste kleinere Lösung sein.
Erwartete Komplexität
Zeit O(n), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.