Daily Temperatures

Q: Jaka jest złożoność czasowa problemu Daily Temperatures?

Rozwiązanie ze stosem monotonicznym działa w czasie O(n) i wymaga O(n) dodatkowej pamięci. Każdy dzień jest dodawany na stos raz i zdejmowany z niego najwyżej raz, więc pętla wewnętrzna wykonuje się najwyżej n razy w całym przebiegu. Skanowanie do przodu od każdego dnia zajmuje O(n²) czasu, czyli około 5 × 10^7 porównań dla 10^4 dni bez cieplejszego dnia.

Q: Dlaczego stos przechowuje indeksy zamiast temperatur?

Odpowiedzią dla danego dnia jest odległość, today - day , więc potrzebujesz pozycji tego dnia. Indeks informuje również, który wpis w tablicy odpowiedzi należy wypełnić po zdjęciu dnia ze stosu. Temperaturę można pobrać jednym odwołaniem jako temperatures[day] , więc jej przechowywanie nic nie daje.

Q: Czy zadanie Daily Temperatures można rozwiązać bez stosu?

Tak. Idź od ostatniego dnia do pierwszego, a dla dnia i zacznij od j = i+1 . Dopóki dzień j nie jest cieplejszy, przeskakuj do dnia wskazywanego przez odpowiedź dla j , j + answer[j] ; jeśli answer[j] wynosi 0, nie istnieje żaden cieplejszy dzień i dzień i również otrzymuje 0. Przeskoki pomijają każdy dzień, który nie może być odpowiedzią, każdy dzień jest pomijany najwyżej raz, a złożoność czasowa pozostaje równa O(n) , bez dodatkowej pamięci poza tablicą odpowiedzi.

ŚrednieStos monotoniczny

+10

Otrzymujesz temperaturę każdego dnia w ciągu kolejnych dni: temperatures[i] to temperatura w dniu i. Dla każdego dnia oblicz, ile dni trzeba po nim czekać, aż nadejdzie dzień z wyższą temperaturą. Jeśli później nie nadejdzie dzień z wyższą temperaturą, czas oczekiwania dla tego dnia wynosi 0.

Zwróć tablicę tej samej długości, w której element i oznacza czas oczekiwania dla dnia i.

Funkcja

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

temperaturesinteger-array: temperatura każdego dnia, w kolejności
Zwracainteger-array: dla każdego dnia liczba dni do cieplejszego dnia lub 0, jeśli taki dzień nie nadejdzie

Ograniczenia

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
„Cieplej” oznacza ściśle wyższą temperaturę: późniejszy dzień z taką samą temperaturą się nie liczy.

Przykłady

Wejście: temperatures = [71, 69, 72, 70, 70, 75, 68]
Wyjście: [2, 1, 3, 2, 1, 0, 0]
Wyjaśnienie: Temperatura w dniu 0 wynosi 71, a pierwszy cieplejszy dzień to dzień 2 z temperaturą 72, więc trzeba poczekać 2 dni. W dniach 3 i 4 temperatura wynosi 70: drugi dzień z temperaturą 70 nie jest cieplejszy, więc w dniu 3 trzeba czekać do dnia 5 z temperaturą 75, czyli 2 dni. Po dniach z temperaturą 75 lub 68 nie ma już cieplejszych dni, więc dla obu wynik wynosi 0.

+13 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Temperatury przyjmują tylko 71 wartości, od 30 do 100. Jak tablica indeksowana temperaturą mogłaby udzielić odpowiedzi dla każdego dnia podczas jednego przebiegu od prawej do lewej i jaki jest koszt tego przebiegu?

Rozwiązanie

W przypadku jednego dnia odpowiedzią jest skanowanie do przodu, ale skanowanie od każdego dnia powtarza tę samą pracę, a gdy ciepłe dni są rzadkie, każde skanowanie przebiega do końca tablicy. Rozwiązaniem jest sprawienie, by każdy dzień udzielał odpowiedzi wcześniejszym dniom, zamiast pytać o późniejsze: stos indeksów, które wciąż czekają, uporządkowany według temperatur, pozwala uzyskać wszystkie odpowiedzi w jednym przebiegu.

Skanuj do przodu każdego dnia

Poprawne, ale nie kończy się na największych testach

Intuicja

Zrób to, co nakazuje treść zadania. Dla dnia i sprawdź dzień i+1, potem i+2 i tak dalej, aż trafisz na pierwszy dzień, którego temperatura jest ściśle wyższa. Odległość j-i jest odpowiedzią. Jeśli dotrzesz do końca, nie znajdując takiego dnia, odpowiedzią pozostaje 0.

To poprawne, ponieważ skanowanie odwiedza kolejne dni w porządku, więc pierwszy napotkany cieplejszy dzień jest pierwszym, jaki istnieje. Zatrzymanie się właśnie wtedy też ma znaczenie: skanowanie, które trwałoby dalej, zapisałoby ostatni cieplejszy dzień.

Ta metoda jest powolna, gdy cieplejsze dni są daleko lub ich brakuje. Jeśli wszystkie 10^4 dni mają tę samą temperaturę, żadne skanowanie nie zatrzymuje się wcześniej: dzień 0 sprawdza 9,999 dni, dzień 1 sprawdza 9,998, a łącznie daje to około n²/2 = 5 × 10^7 porównań. Skanowania nakładają się też na siebie: dzień 1 przechodzi niemal dokładnie tę samą drogę co dzień 0 i niczego się z niego nie dowiaduje.

Algorytm

Utwórz tablicę odpowiedzi wypełnioną zerami, po jednym wpisie na każdy dzień.
Dla każdego dnia i przeszukuj dni j od i+1 do ostatniego dnia.
Przy pierwszym j, dla którego temperatures[j] > temperatures[i], zapisz j-i i zakończ przeszukiwanie.
Zwróć tablicę odpowiedzi; dni, dla których przeszukiwanie niczego nie znalazło, zachowują wartość 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

Monotoniczny stos dni oczekiwania

Intuicja

Odwróć pytanie. Zamiast każdego dnia pytać, który dzień następuje po nim, przejdź po dniach raz i pozwól, by każdy nowy dzień odpowiadał wcześniejszym dniom, które przewyższa temperaturą. Dni, które jeszcze nie mają odpowiedzi, przechowuj na stosie jako indeksy. Gdy nadejdzie dzisiejszy dzień, każdy oczekujący dzień, który jest chłodniejszy od dzisiejszego, znalazł swój pierwszy cieplejszy dzień: dzisiejszy. Zdejmij je ze stosu i wpisz today - day jako odpowiedź. Następnie dodaj dzisiejszy dzień na stos, gdzie będzie czekał na swój cieplejszy dzień.

Przejdźmy przez [71, 69, 72, 70, 70, 75, 68]. Dzień 0 (71) zostaje dodany na stos. Dzień 1 (69) nie jest cieplejszy niż 71, więc zostaje dodany na wierzch: stos zawiera dni [0, 1]. Dzień 2 (72) zdejmuje ze stosu dzień 1 (czekał 1 dzień), a następnie dzień 0 (czekał 2 dni), po czym sam zostaje dodany na stos. Dni 3 i 4 (70 i 70) zostają dodane na stos; drugie 70 nie zdejmuje pierwszego ze stosu, ponieważ taka sama temperatura nie jest cieplejsza. Dzień 5 (75) zdejmuje ze stosu dzień 4 (czekał 1 dzień), dzień 3 (czekał 2 dni) i dzień 2 (czekał 3 dni). Dzień 6 (68) zostaje dodany na stos. Dni 5 i 6 nadal czekają na końcu, więc przypisuje się im 0. Odpowiedź to [2, 1, 3, 2, 1, 0, 0].

Dlaczego liczy się tylko wierzchołek stosu: temperatury na stosie nigdy nie rosną od dołu do góry. Dzień zostaje dodany na stos dopiero po zdjęciu ze stosu wszystkich chłodniejszych dni znajdujących się nad nim, więc wszystko, co znajduje się pod nim, ma co najmniej tak wysoką temperaturę jak on. Jeśli dzisiejszy dzień nie jest cieplejszy niż dzień na wierzchołku, nie jest też cieplejszy niż jakikolwiek dzień poniżej, więc możesz przestać zdejmować elementy ze stosu. Dzień opuszcza stos, gdy tylko pojawi się pierwszy cieplejszy dzień, więc zapisany czas oczekiwania jest czasem do pierwszego cieplejszego dnia, a nie do najcieplejszego dnia.

Stos przechowuje indeksy, a nie temperatury, ponieważ odpowiedzią jest odległość i musisz wiedzieć, który wpis w tablicy odpowiedzi uzupełnić. Odczytaj temperaturę za pomocą temperatures[day]. Każdy dzień jest dodawany na stos raz i zdejmowany z niego co najwyżej raz, więc łączna liczba zdjęć ze stosu podczas całego przejścia wynosi najwyżej n, a całkowity czas działania to O(n), mimo że jeden dzień może zdjąć ze stosu wiele elementów.

Algorytm

Utwórz tablicę odpowiedzi wypełnioną zerami i pusty stos indeksów.
Dla każdego dnia today, dopóki dzień na szczycie stosu jest chłodniejszy niż dzisiaj, zdejmij go ze stosu i ustaw jego odpowiedź na wartość today pomniejszoną o jego indeks.
Umieść today na stosie.
Po pętli dni pozostałe na stosie nie mają cieplejszego dnia, więc ich wartość pozostaje równa 0. Zwróć tablicę odpowiedzi.

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

Pułapki i przypadki brzegowe

Pętla stosu składa się z kilku wierszy; błędy kryją się w porównaniu i w tym, co znajduje się na stosie.

Zdejmowanie elementu ze stosu przy użyciu >= zamiast >. Dzień z taką samą temperaturą nie jest cieplejszy. W [71, 69, 72, 70, 70, 75, 68] dzień 3 czeka 2 dni na 75, a nie 1 dzień na drugie 70.
Umieszczanie na stosie temperatur zamiast indeksów. Odpowiedzią jest odległość w dniach, a do jej obliczenia i ustalenia, który element uzupełnić, potrzebujesz indeksu.
Używanie if, gdy potrzebujesz while. Jeden ciepły dzień może jednocześnie wskazać odpowiedź dla wielu oczekujących dni: w pierwszym przykładzie 75 wskazuje odpowiedź dla trzech dni.
Zwracanie cieplejszej temperatury lub indeksu cieplejszego dnia. Wynikiem jest liczba dni oczekiwania, j-i.
Pozostawianie dni, które nadal są na stosie, bez ustawionej odpowiedzi. Ich odpowiedź to 0; w C zaalokuj pamięć na odpowiedź za pomocą calloc albo ją wypełnij, ponieważ pamięć przydzielona przez malloc zawiera śmieci.
Pozwalanie, by skanowanie do przodu wykraczało poza pierwszy cieplejszy dzień. Bez break zostanie zapisany ostatni cieplejszy dzień zamiast pierwszego.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu Daily Temperatures?

Rozwiązanie ze stosem monotonicznym działa w czasie O(n) i wymaga O(n) dodatkowej pamięci. Każdy dzień jest dodawany na stos raz i zdejmowany z niego najwyżej raz, więc pętla wewnętrzna wykonuje się najwyżej n razy w całym przebiegu. Skanowanie do przodu od każdego dnia zajmuje O(n²) czasu, czyli około 5 × 10^7 porównań dla 10^4 dni bez cieplejszego dnia.

Dlaczego stos przechowuje indeksy zamiast temperatur?

Odpowiedzią dla danego dnia jest odległość, today - day, więc potrzebujesz pozycji tego dnia. Indeks informuje również, który wpis w tablicy odpowiedzi należy wypełnić po zdjęciu dnia ze stosu. Temperaturę można pobrać jednym odwołaniem jako temperatures[day], więc jej przechowywanie nic nie daje.

Czy zadanie Daily Temperatures można rozwiązać bez stosu?

Tak. Idź od ostatniego dnia do pierwszego, a dla dnia i zacznij od j = i+1. Dopóki dzień j nie jest cieplejszy, przeskakuj do dnia wskazywanego przez odpowiedź dla j, j + answer[j]; jeśli answer[j] wynosi 0, nie istnieje żaden cieplejszy dzień i dzień i również otrzymuje 0. Przeskoki pomijają każdy dzień, który nie może być odpowiedzią, każdy dzień jest pomijany najwyżej raz, a złożoność czasowa pozostaje równa O(n), bez dodatkowej pamięci poza tablicą odpowiedzi.

Jaki związek ma zadanie Daily Temperatures z zadaniem Next Greater Element?

To samo pytanie zadawane dla każdej pozycji: znajdź następną większą wartość po prawej stronie. Next Greater Element zwraca tę wartość; Daily Temperatures zwraca odległość do niej, dlatego stos przechowuje indeksy. Ten sam stos monotoniczny, z odwróconym warunkiem zdejmowania elementów przy mniejszej wartości, odpowiada również na pytania o następny mniejszy element.

Python

def dailyTemperatures(temperatures):
    # Wpisz tutaj kod

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

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