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 O(n) zusätzlichen Speicherplatz. Jeder Tag wird einmal auf den Stapel gelegt und höchstens einmal entfernt, daher wird die innere Schleife während des gesamten Durchlaufs höchstens n -mal ausgeführt. Das Vorwärtssuchen ab jedem Tag benötigt O(n²) Zeit, etwa 5 × 10^7 Vergleiche bei 10^4 Tagen ohne wärmeren Tag.

Q: Warum speichert der Stack Indizes statt Temperaturen?

Die Antwort für einen Tag ist eine Entfernung, today - day , also brauchst du die Position des Tages. Der Index verrät außerdem, welchen Eintrag des Antwort-Arrays du ausfüllen musst, wenn der Tag vom Stapel genommen wird. Die Temperatur ist mit temperatures[day] nur einen Zugriff entfernt, sie zusätzlich zu speichern bringt also nichts.

Q: Kann man Daily Temperatures ohne einen Stack lösen?

Ja. Gehe vom letzten Tag zum ersten und starte für Tag i bei j = i+1 . Solange Tag j nicht wärmer ist, springe zu dem Tag, der j beantwortet: j + answer[j] . Wenn answer[j] 0 ist, gibt es keinen wärmeren Tag und Tag i erhält ebenfalls 0. Durch die Sprünge werden alle Tage übersprungen, die nicht die Antwort sein können; jeder Tag wird höchstens einmal übersprungen. Die Laufzeit bleibt O(n) , und außer dem Antwort-Array wird kein zusätzlicher Speicher benötigt.

MittelMonotoner Stack

+10

Du erhältst die Temperatur jedes Tages in einer Reihe von Tagen: 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. Wenn später kein wärmerer Tag kommt, beträgt die Wartezeit für diesen Tag 0.

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 Reihe nach
Gibt zurückinteger-array: für jeden Tag die Anzahl der Tage bis zu einem wärmeren Tag oder 0, wenn keiner folgt

Einschränkungen

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
Wärmer bedeutet strikt höher: 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 ist 71 und der erste wärmere Tag ist Tag 2 mit 72, also wartet es 2 Tage. Die Tage 3 und 4 haben beide 70: Das zweite 70 ist nicht wärmer, daher wartet Tag 3 bis Tag 5 mit 75, also 2 Tage. Nach 75 oder 68 ist nichts wärmer, daher erhalten beide 0.

+13 versteckte Tests beim Einreichen

Weiterführende Frage

Die Temperaturen nehmen nur 71 Werte an, von 30 bis 100. Wie könnte eine nach Temperatur indizierte Tabelle jeden Tag in einem Durchgang von rechts nach links beantworten, und wie viel kostet dieser Durchgang?

Lösung

Für einen einzelnen Tag lautet die Antwort: eine Vorwärtssuche. Eine Suche von jedem Tag aus wiederholt jedoch dieselbe Arbeit, und wenn warme Tage selten sind, läuft jede Suche bis zum Ende des Arrays. Die Lösung besteht darin, jeden Tag die früheren Tage beantworten zu lassen, statt nach den späteren zu fragen: Ein Stapel von Indizes, die noch warten, bleibt nach Temperatur sortiert und liefert jede Antwort in einem einzigen Durchlauf.

Von jedem Tag aus vorwärts suchen

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

Idee

Tu, was die Aufgabe verlangt. Betrachte für den Tag i den Tag i+1, dann i+2 und so weiter, und höre beim ersten Tag auf, dessen Temperatur strikt höher ist. Der Abstand j-i ist die Antwort. Wenn du das Ende erreichst, ohne einen solchen Tag zu finden, bleibt die Antwort 0.

Das ist korrekt, weil der Durchlauf die späteren Tage der Reihe nach besucht und der erste wärmere Tag, auf den er trifft, somit der erste wärmere Tag überhaupt ist. Auch das sofortige Anhalten ist wichtig: Ein Durchlauf, der weiterläuft, würde stattdessen den letzten wärmeren Tag erfassen.

Das Verfahren ist langsam, wenn wärmere Tage weit entfernt sind oder fehlen. Wenn alle 10^4 Tage dieselbe Temperatur haben, hält kein Durchlauf vorzeitig an: Tag 0 prüft 9,999 Tage, Tag 1 prüft 9,998, und insgesamt sind es etwa n²/2 = 5 × 10^7 Vergleiche. Außerdem überschneiden sich die Durchläufe: Tag 1 legt fast genau denselben Weg zurück wie Tag 0 und lernt nichts daraus.

Algorithmus

Erstelle ein Antwort-Array aus Nullen mit einem Eintrag pro Tag.
Durchsuche für jeden Tag i die Tage j von i+1 bis zum letzten Tag.
Speichere beim ersten j, für das temperatures[j] > temperatures[i] gilt, 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

Drehe die Frage um. Frage nicht für jeden Tag, was danach kommt, sondern gehe die Tage einmal durch und lass jeden neuen Tag die früheren Tage beantworten, die er übertrifft. Bewahre die Tage, für die es noch keine Antwort gibt, als Indizes auf einem Stack auf. Wenn der heutige Tag kommt, hat jeder wartende Tag, der kälter als heute ist, seinen ersten wärmeren Tag gefunden: heute. Entferne jeden davon und schreibe today - day als seine Antwort. Lege dann den heutigen Tag auf den Stack, der nun auf seinen eigenen wärmeren Tag wartet.

Gehe [71, 69, 72, 70, 70, 75, 68] durch. Tag 0 (71) wird auf den Stack gelegt. Tag 1 (69) ist nicht wärmer als 71, also wird er oben daraufgelegt: Der Stack enthält die Tage [0, 1]. Tag 2 (72) entfernt Tag 1 (Wartezeit 1) und dann Tag 0 (Wartezeit 2) vom Stack und wird anschließend auf den Stack gelegt. Die Tage 3 und 4 (70 und 70) werden auf den Stack gelegt; die zweite 70 entfernt die erste nicht vom Stack, weil gleich nicht wärmer bedeutet. Tag 5 (75) entfernt Tag 4 (Wartezeit 1), Tag 3 (Wartezeit 2) und Tag 2 (Wartezeit 3) vom Stack. Tag 6 (68) wird auf den Stack gelegt. Die Tage 5 und 6 warten am Ende noch, also behalten sie den Wert 0. Die Antwort lautet [2, 1, 3, 2, 1, 0, 0].

Warum nur das oberste Element zählt: Die Temperaturen auf dem Stack steigen von unten nach oben nie an. Ein Tag wird erst dann auf den Stack gelegt, wenn alle kälteren Tage über ihm entfernt wurden, also ist alles unter ihm mindestens genauso warm. Wenn heute nicht wärmer als das oberste Element ist, ist heute auch nicht wärmer als irgendetwas darunter, und du kannst aufhören, Elemente vom Stack zu entfernen. Ein Tag verlässt den Stack, sobald der erste wärmere Tag auftaucht. Die erfasste Wartezeit gilt also bis zum ersten wärmeren Tag, nicht bis zum wärmsten.

Der Stack enthält Indizes, keine Temperaturen, weil die Antwort eine Entfernung ist und du wissen musst, welchen Eintrag der Antwort du ausfüllen sollst. Lies die Temperatur mit temperatures[day] ab. Jeder Tag wird einmal auf den Stack gelegt und höchstens einmal entfernt, daher summieren sich alle Entfernungen über den gesamten Durchlauf auf höchstens n, und die Gesamtlaufzeit beträgt O(n), obwohl an einem einzelnen Tag viele Elemente vom Stack entfernt werden können.

Algorithmus

Erstelle ein Antwort-Array mit Nullen und einen leeren Stapel mit Indizes.
Für jeden Tag today: Solange der Tag oben auf dem Stapel kälter als heute ist, 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 Antwort-Array 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

Die Stapelschleife umfasst nur wenige Zeilen; die Fehler stecken im Vergleich und darin, was der Stapel enthält.

Entfernen mit >= statt mit >. Ein Tag mit derselben Temperatur ist nicht wärmer. In [71, 69, 72, 70, 70, 75, 68] wartet Tag 3 zwei Tage auf 75, nicht einen Tag auf die zweite 70.
Temperaturen statt Indizes auf den Stapel legen. Die Antwort ist ein Abstand in Tagen, und du brauchst den Index, um ihn zu berechnen und zu wissen, welchen Eintrag du füllen musst.
if verwenden, wo du while brauchst. Ein warmer Tag kann mehrere wartende Tage auf einmal beantworten: 75 beantwortet im ersten Beispiel drei davon.
Die wärmere Temperatur oder den Index des wärmeren Tages zurückgeben. Die Ausgabe gibt an, wie viele Tage du warten musst: j-i.
Die Tage, die noch auf dem Stapel liegen, ohne Wert lassen. Ihre Antwort ist 0; weise in C die Antwort mit calloc zu oder fülle sie, denn der Speicher von malloc enthält Müllwerte.
Den Vorwärtsdurchlauf über den ersten wärmeren Tag hinauslaufen lassen. Ohne break wird der letzte wärmere Tag statt des ersten erfasst.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Daily Temperatures?

Die Lösung mit dem monotonen Stapel benötigt O(n) Zeit und O(n) zusätzlichen Speicherplatz. Jeder Tag wird einmal auf den Stapel gelegt und höchstens einmal entfernt, daher wird die innere Schleife während des gesamten Durchlaufs höchstens n-mal ausgeführt. Das Vorwärtssuchen ab jedem Tag benötigt O(n²) Zeit, etwa 5 × 10^7 Vergleiche bei 10^4 Tagen ohne wärmeren Tag.

Warum speichert der Stack Indizes statt Temperaturen?

Die Antwort für einen Tag ist eine Entfernung, today - day, also brauchst du die Position des Tages. Der Index verrät außerdem, welchen Eintrag des Antwort-Arrays du ausfüllen musst, wenn der Tag vom Stapel genommen wird. Die Temperatur ist mit temperatures[day] nur einen Zugriff entfernt, sie zusätzlich zu speichern bringt also nichts.

Kann man Daily Temperatures ohne einen Stack lösen?

Ja. Gehe vom letzten Tag zum ersten und starte für Tag i bei j = i+1. Solange Tag j nicht wärmer ist, springe zu dem Tag, der j beantwortet: j + answer[j]. Wenn answer[j] 0 ist, gibt es keinen wärmeren Tag und Tag i erhält ebenfalls 0. Durch die Sprünge werden alle Tage übersprungen, die nicht die Antwort sein können; jeder Tag wird höchstens einmal übersprungen. Die Laufzeit bleibt O(n), und außer dem Antwort-Array wird kein zusätzlicher Speicher benötigt.

Wie hängen tägliche Temperaturen mit dem nächstgrößeren 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 monotone Stack, so angepasst, dass er bei einem kleineren Wert Elemente entfernt, beantwortet auch Fragen nach dem nächsten kleineren Element.

Python

def dailyTemperatures(temperatures):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

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