Stock Span Problem
Du erhältst für jeden Tag den Schlusskurs einer Aktie: prices[i] ist der Kurs am Tag i. Die Spanne des Tages i ist die Anzahl der aufeinanderfolgenden Tage bis einschließlich Tag i, an denen der Kurs kleiner oder gleich prices[i] war.
Gib die Spanne jedes Tages in derselben Reihenfolge wie prices zurück. Jede Spanne beträgt mindestens 1, da ein Tag immer für sich selbst zählt.
Funktion
- pricesinteger-array
- der Preis an jedem Tag, der Reihe nach
- Gibt zurückinteger-array
- die Zeitspanne jedes Tages, in derselben Reihenfolge
Einschränkungen
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- Ein früherer Tag mit demselben Preis zählt zur Spanne; nur ein strikt höherer Preis stoppt sie.
Beispiele
- Eingabe
- prices = [31, 27, 14, 21, 30, 18, 40]
- Ausgabe
- [1, 1, 1, 2, 4, 1, 7]
- Erklärung
- Tag 3 erreicht bei 21 einen Wert über 14 zurück und endet bei 27: Spanne 2. Tag 4 endet bei 30 bei 31: Spanne 4. Tag 6 übertrifft bei 40 alle früheren Preise und umfasst alle 7 Tage.
- Eingabe
- prices = [8, 8, 3, 8]
- Ausgabe
- [1, 2, 1, 4]
- Erklärung
- Gleiche Preise zählen mit, daher deckt Tag 1 mit einem Preis von 8 Tag 0 ab und erhält den Wert 2. Tag 3 mit einem Preis von 8 deckt den Wert 3 und beide früheren 8er ab, eine Spanne von 4.
- Eingabe
- prices = [50, 40, 30, 20]
- Ausgabe
- [1, 1, 1, 1]
- Erklärung
- Jeder Tag ist günstiger als der Tag davor, daher reicht kein Span über den jeweiligen Tag hinaus zurück und jeder Span ist 1.
Weiterführende Frage
Die Preise treffen nun einzeln ein, und du musst jede Spanne melden, sobald der jeweilige Preis eintrifft. Welcher Ansatz funktioniert weiterhin, und was behält er zwischen den Aufrufen bei?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Von jedem Tag aus rückwärts zu zählen, wiederholt die Arbeit: Bei 8000 Tagen zum selben Preis geht man allein am letzten Tag 8000 Tage zurück. Wenn du von heute aus zurückgehst, welche früheren Tage kannst du endgültig überspringen?
Sobald der heutige Preis mindestens so hoch ist wie der eines früheren Tages, kann dieser frühere Tag niemals derjenige sein, der eine spätere Spanne beendet: Der heutige Tag liegt näher und ist mindestens genauso teuer. Nur die Tage, die teurer sind als alle Tage nach ihnen, sind noch relevant, und ihre Preise fallen vom ältesten zum neuesten Tag.
Gehe die Tage der Reihe nach durch und behalte die früheren Tage, die noch relevant sind, als Indizes auf einem Stack. Bevor du die Antwort für den heutigen Tag ermittelst, entferne alle Tage vom Stack, deren Preis höchstens dem heutigen Preis entspricht. Ein leerer Stack bedeutet, dass die Spanne bis zu Tag 0 zurückreicht; andernfalls endet sie einen Tag nach dem Tag, der oben auf dem Stack liegt. Füge dann den heutigen Tag hinzu.
Lösung
Die Spanne eines Tages endet am nächstgelegenen früheren Tag mit einem strikt höheren Preis. Das Zurückgehen, um ihn zu finden, kostet bis zu n Schritte pro Tag. Behalte stattdessen nur die Tage, die die Spanne eines zukünftigen Tages noch begrenzen können: Ein Stapel von Indizes mit strikt fallenden Preisen findet in einem Durchlauf alle Grenzen.
Von jedem Tag aus rückwärts zählen
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Folge der Definition. Gehe für den Tag i jeweils einen Tag zurück, solange der Preis dort höchstens prices[i] beträgt, und zähle auch den Tag i mit. Der erste strikt höhere Preis oder der Anfang des Arrays beendet den Durchlauf.
Kein Durchlauf verwendet einen früheren erneut. Bei gleichbleibenden oder steigenden Preisen reicht jeder Durchlauf bis zu Tag 0 zurück: n = 10^4 Tage bedeuten etwa 5 × 10^7 Schritte.
Algorithmus
- Erstelle
span, ein Array, das genauso lang ist wieprices. - Setze für jeden Tag
ieinen Zähler auf 0 und einen Zeigerjaufi. - Solange
j ≥ 0undprices[j] ≤ prices[i]gilt, addiere 1 zum Zähler und bewegejeinen Tag zurück. - Speichere den Zähler in
span[i]. Gib nach dem letzten Tagspanzurück.
def stockSpan(prices):
span = []
for i in range(len(prices)):
count = 0
j = i
# Count today and every earlier day in a row that is not more expensive.
while j >= 0 and prices[j] <= prices[i]:
count += 1
j -= 1
span.append(count)
return spanMonotoner Stapel höherer Tage
Idee
Nenne den nächstgelegenen früheren Tag mit einem strikt höheren Preis den Blockierer. Die Spanne ist today - blocker oder today + 1, wenn es keinen gibt.
Im ersten Beispiel kostet Tag 3 21 und Tag 4 kostet 30. Jeder spätere Durchlauf erreicht zuerst Tag 4, und jeder Preis, der über 30 hinauskommt, kommt auch über 21 hinaus, sodass Tag 3 nie wieder blockieren kann. Allgemein gilt: Wenn der heutige Tag erreicht ist, ist jeder frühere Kandidat mit einem Preis kleiner oder gleich dem heutigen Preis erledigt: Entferne ihn vom Stapel. Der oben verbleibende Tag ist der Blockierer des heutigen Tages. Dann lege den heutigen Tag auf den Stapel.
Die Preise auf dem Stapel fallen von unten nach oben strikt, daher ist der erste verbleibende Preis der nächstgelegene höhere Preis. Im ersten Beispiel entfernt Tag 4 die Tage 3 und 1 vom Stapel und stoppt bei Tag 0, was eine Spanne von 4 - 0 = 4 ergibt. Jeder Tag wird einmal auf den Stapel gelegt und höchstens einmal entfernt, daher läuft der Durchlauf in O(n).
Algorithmus
- Erstelle das
span-Array und einen leeren Stack für Tagesindizes. - Entferne für jeden Tag
todayIndizes vom Stack, solange ihr Preis kleiner oder gleichprices[today]ist. - Wenn der Stack leer ist, ist der Span
today + 1; andernfalls ist ertodayminus der Index an der Spitze. - Lege
todayauf den Stack und gehe zum nächsten Tag. Gibspanzurück.
def stockSpan(prices):
span = [0] * len(prices)
higher = [] # indices of earlier days, prices strictly falling toward the top
for today, price in enumerate(prices):
# A day that is not more expensive than today can never stop a later span.
while higher and prices[higher[-1]] <= price:
higher.pop()
# The span reaches back to the nearest more expensive day, or to day 0.
span[today] = today - higher[-1] if higher else today + 1
higher.append(today)
return span
Stolperfallen und Grenzfälle
- Entfernen bei
<statt bei<=. In[8, 8, 3, 8]beträgt die Spanne am letzten Tag 4; beim früheren 8 anzuhalten ergibt 2. todaystatttoday + 1zu schreiben, wenn der Stapel leer ist. Tag 0 muss 1 erhalten, nicht 0.- Pro Tag nur einmal ein Element entfernen. Im ersten Beispiel muss 40 die Tage 5, 4 und 0 abräumen. Wenn du nach Tag 5 stoppst, scheint Tag 4 der Blockierer zu sein, was eine Spanne von 2 statt 7 ergibt.
- In Lua und R beginnen Arrays bei 1. Bei 1-basierten Indizes ist die Spanne bei leerem Stapel
today, nichttoday + 1.
Häufige Fragen4
Wie hoch ist die Zeitkomplexität des Stock-Span-Problems?
O(n) Laufzeit und O(n) zusätzlicher Speicherplatz mit dem monotonen Stapel, da jeder Tag den Stapel höchstens einmal verlässt. Das rückwärts Durchlaufen ab jedem Tag hat O(n²) Laufzeit, wenn die Preise ständig steigen oder gleich bleiben.
Soll der Stack Preise oder Tagesindizes speichern?
Tagesindizes. Die Spanne ist eine Anzahl von Tagen, und nur der Index des Blockierers gibt dir diese an. prices[index] liest den Preis für den Vergleich aus.
Kann das Stock-Span-Problem ohne einen separaten Stack gelöst werden?
Ja. Beginne bei j = today - 1; solange j ≥ 0 und prices[j] ≤ prices[today] gilt, springe zu j - span[j], da jeder Tag innerhalb dieser Spanne einen Preis von höchstens prices[j] hat. Die Spanne ist today - j. Die Sprünge landen nur auf Tagen, die der Stack enthalten würde, sodass der Durchlauf O(n) bleibt.
Ist das Stock-Spannen-Problem ein Problem des vorherigen größeren Elements?
Ja, gemessen in Tagen: Für jeden Tag findest du den nächstgelegenen früheren Tag mit einem strikt höheren Preis und gibst an, wie viele Tage er zurückliegt. Ändere die Scanrichtung oder den Vergleich, und derselbe Stapel liefert das nächste größere, das nächste kleinere oder das vorherige kleinere Element.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def stockSpan(prices):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
prices = [31, 27, 14, 21, 30, 18, 40]
Erwartete Ausgabe
[1, 1, 1, 2, 4, 1, 7]