Daily Temperatures

Q: Wie hoch ist die Zeitkomplexität von Daily Temperatures?

Die Lösung mit dem monotonen Stapel benötigt O(n) Zeit und zusätzlichen Speicherplatz von O(n) O(n²) Zeit, also etwa 5 × 10^7 Vergleiche bei 10^4 Tagen ohne wärmeren Tag.

MittelMonotoner Stack

+10

temperatures[i] ist die Temperatur am Tag i. Zähle für jeden Tag, wie viele Tage du danach warten musst, bis ein strikt wärmerer Tag kommt, oder 0, wenn später kein wärmerer Tag kommt. Gib ein Array derselben Länge zurück, in dem der Eintrag i die Wartezeit für Tag i angibt.

Funktion

dailyTemperatures(temperatures: integer-array) → integer-array

temperaturesinteger-array: die Temperatur jedes Tages, der Reihenfolge nach
Gibt zurückinteger-array: für jeden Tag die Anzahl der Tage bis zu einem wärmeren Tag oder 0, falls keiner kommt

Einschränkungen

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
Wärmer heißt: strikt höhere Temperatur; ein späterer Tag mit derselben Temperatur zählt nicht.

Beispiele

Eingabe: temperatures = [71, 69, 72, 70, 70, 75, 68]
Ausgabe: [2, 1, 3, 2, 1, 0, 0]
Erklärung: Tag 0 (71) wartet 2 Tage auf 72. Tag 3 (70) überspringt die gleiche 70 an Tag 4 und wartet 2 Tage auf 75. Nach 75 oder 68 ist nichts wärmer, daher erhalten beide 0.

Weiterführende Frage

Temperaturen können nur 71 Werte annehmen, von 30 bis 100. Wie könnte eine nach Temperatur indizierte Tabelle jeden Tag in einem Durchlauf von rechts nach links beantworten, und zu welchen Kosten?

Lösung

Ein Vorwärtsscan von jedem Tag aus wiederholt Arbeit, und wenn warme Tage selten sind, läuft jeder Scan bis zum Ende. Gehe stattdessen die Tage einmal durch und lass jeden neuen Tag die früheren Tage beantworten, die er übertrifft. Die Tage, die noch warten, liegen auf einem Stapel, dessen Temperaturen von unten nach oben nie ansteigen, sodass jede Antwort in einem Durchgang zustande kommt.

Scanne von jedem Tag aus vorwärts

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Überprüfe für Tag i die Tage i+1, i+2 und so weiter, und halte beim ersten Tag j an, der strikt wärmer ist. Die Antwort lautet j-i oder 0, wenn die Suche das Ende erreicht. Durch das Durchsuchen der Tage der Reihe nach ist der erste wärmere Tag, auf den du triffst, auch der erste, den es gibt.

Wenn alle 10^4 Tage dieselbe Temperatur haben, wird keine Suche vorzeitig beendet: etwa n²/2 = 5 × 10^7 Vergleiche, und Tag 1 legt fast denselben Weg zurück, den Tag 0 bereits zurückgelegt hat.

Algorithmus

Erstelle ein Antwort-Array mit Nullen, einem Eintrag pro Tag.
Durchsuche für jeden Tag i die Tage j von i+1 bis zum letzten Tag.
Speichere beim ersten j mit temperatures[j] > temperatures[i] den Wert j-i und beende die Suche.
Gib das Antwort-Array zurück; bei Tagen, für die die Suche nichts gefunden hat, bleibt der Wert 0.

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i  # the first warmer day, so stop here
                break
    return answer

Monotoner Stapel wartender Tage

Idee

Behalte die Tage, für die es noch keine Antwort gibt, als Indizes auf einem Stapel. Wenn der heutige Tag kommt, entferne alle wartenden Tage, die kälter als heute sind: Heute ist ihr erster wärmerer Tag, also lautet ihre Antwort today - day. Lege dann den heutigen Tag auf den Stapel.

Nur die oberste Position muss überprüft werden. Ein Tag wird erst dann auf den Stapel gelegt, wenn alle kälteren Tage über ihm entfernt wurden; daher steigen die Temperaturen auf dem Stapel von unten nach oben nie an. Wenn heute nicht wärmer als der oberste Tag ist, ist es auch nicht wärmer als irgendein darunterliegender Tag, und du hörst auf, Tage zu entfernen. Im ersten Beispiel entfernt Tag 5 (75) die Tage 4, 3 und 2 mit Wartezeiten von 1, 2 und 3, während die zweite 70 die erste nie entfernt hat, da gleich nicht wärmer bedeutet.

Jeder Tag wird einmal auf den Stapel gelegt und höchstens einmal entfernt, daher summieren sich die Entfernungen auf höchstens n: Laufzeit O(n), auch wenn ein Tag viele entfernen kann.

Algorithmus

Erstelle ein Antwortarray mit Nullen und einen leeren Stapel von Indizes.
Für jeden Tag today: Solange der Tag oben auf dem Stapel kälter ist als heute, nimm ihn vom Stapel und setze seine Antwort auf today minus seinen Index.
Lege today auf den Stapel.
Nach der Schleife haben die Tage, die noch auf dem Stapel liegen, keinen wärmeren Tag und behalten den Wert 0. Gib das Antwortarray zurück.

def dailyTemperatures(temperatures):
    answer = [0] * len(temperatures)
    waiting = []  # indices of days with no warmer day yet, colder toward the top
    for today, temp in enumerate(temperatures):
        # Today is the first warmer day for every colder day on top of the stack.
        while waiting and temperatures[waiting[-1]] < temp:
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)
    # Days still waiting never get a warmer day and keep their 0.
    return answer

Stolperfallen und Grenzfälle

Bei >= statt bei > entfernen. Im ersten Beispiel wartet Tag 3 dann 1 Tag auf die zweite 70 statt 2 Tage auf 75.
Temperaturen statt Indizes auf den Stapel legen. Dann kannst du weder den Abstand berechnen noch erkennen, welchen Eintrag der Antwort du ausfüllen musst.
if verwenden, obwohl du while brauchst. Ein warmer Tag kann viele wartende Tage beantworten: 75 beantwortet im ersten Beispiel drei Tage.
Die Tage, die noch auf dem Stapel liegen, nicht mit einem Wert belegen. Ihre Antwort ist 0; verwende in C calloc, um die Antwort zu reservieren, denn der Speicher von malloc enthält Zufallswerte.
Den Vorwärtsdurchlauf über den ersten wärmeren Tag hinaus laufen lassen. Ohne das break wird stattdessen der letzte wärmere Tag erfasst.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Daily Temperatures?

Die Lösung mit dem monotonen Stapel benötigt O(n) Zeit und zusätzlichen Speicherplatz von O(n)</code), da jeder Tag einmal hinzugefügt und höchstens einmal entfernt wird. Das Vorwärtsscannen ab jedem Tag benötigt <code>O(n²) Zeit, also etwa 5 × 10^7 Vergleiche bei 10^4 Tagen ohne wärmeren Tag.

Kann man Daily Temperatures ohne einen Stack lösen?

Ja. Fülle die Antworten vom letzten Tag aus rückwärts aus und beginne für Tag i bei j = i+1; solange Tag j nicht wärmer ist, springe zu j + answer[j], dem Tag, der j beantwortet. Wenn answer[j] 0 ist, erhält auch Tag i den Wert 0. Die Sprünge überspringen Tage, die i nicht beantworten können: O(n) Zeit, kein zusätzlicher Speicher.

Wie hängen Daily Temperatures und Next Greater Element zusammen?

Es ist dieselbe Frage für jede Position: Finde den nächsten größeren Wert rechts davon. Next Greater Element gibt diesen Wert zurück; Daily Temperatures gibt zurück, wie weit er entfernt ist. Deshalb enthält der Stack Indizes. Derselbe Stack beantwortet Fragen nach dem nächsten kleineren Element, wenn er so angepasst wird, dass er bei einem kleineren Wert Elemente entfernt.

def dailyTemperatures(temperatures):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

temperatures = [71, 69, 72, 70, 70, 75, 68]

Erwartete Ausgabe

[2, 1, 3, 2, 1, 0, 0]