Daily Temperatures

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

Rozwiązanie z użyciem stosu monotonicznego działa w czasie O(n) i wymaga O(n) dodatkowej pamięci, ponieważ każdy dzień jest dodawany na stos raz i zdejmowany z niego najwyżej raz. Przeszukiwanie 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.

ŚrednieStos monotoniczny

+10

temperatures[i] to temperatura w dniu i. Dla każdego dnia policz, ile dni trzeba czekać po nim, aż nadejdzie dzień z ściśle wyższą temperaturą, lub 0, jeśli później nie nadejdzie dzień z wyższą temperaturą. Zwróć tablicę o tej samej długości, w której wpis i oznacza czas oczekiwania dla dnia i.

Funkcja

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

temperaturesinteger-array: temperatura każdego dnia, po kolei
Zwracainteger-array: dla każdego dnia liczba dni do cieplejszego dnia albo 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: Dzień 0 (71) czeka 2 dni na 72. Dzień 3 (70) pomija równe 70 w dniu 4 i czeka 2 dni na 75. Żadna temperatura po 75 ani 68 nie jest wyższa, więc obie otrzymują 0.

Pytanie dodatkowe

Temperatury przyjmują tylko 71 wartości, od 30 do 100. Jak tablica indeksowana temperaturą mogłaby odpowiedzieć na każdy dzień w jednym przebiegu od prawej do lewej i jakim kosztem?

Rozwiązanie

Skanowanie w przód od każdego dnia powtarza pracę, a gdy ciepłe dni zdarzają się rzadko, każde skanowanie trwa aż do końca. Zamiast tego przejdź przez dni raz i pozwól, by każdy nowy dzień odpowiadał wcześniejszym dniom, które przewyższa temperaturą. Dni, które wciąż czekają, pozostają na stosie, na którym temperatury nigdy nie rosną od dołu do góry, dzięki czemu wszystkie odpowiedzi uzyskasz w jednym przebiegu.

Skanuj do przodu każdego dnia

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

Intuicja

Dla dnia i sprawdzaj dni i+1, i+2 i tak dalej, a następnie zatrzymaj się przy pierwszym dniu j, w którym temperatura jest ściśle wyższa. Odpowiedzią jest j-i albo 0, jeśli skanowanie dotrze do końca. Skanowanie po kolei sprawia, że pierwszy napotkany cieplejszy dzień jest tym pierwszym, który istnieje.

Jeśli wszystkie 10^4 dni mają tę samą temperaturę, żadne skanowanie nie zatrzyma się wcześniej: około n²/2 = 5 × 10^7 porównań, a dzień 1 pokonuje niemal tę samą drogę, którą dzień 0 już pokonał.

Algorytm

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

Przechowuj na stosie indeksy dni, które nie mają jeszcze odpowiedzi. Gdy nadejdzie dzisiejszy dzień, zdejmuj ze stosu wszystkie oczekujące dni chłodniejsze niż dzisiaj: dzisiaj jest dla nich pierwszym cieplejszym dniem, więc odpowiedzią jest today - day. Następnie dodaj dzisiejszy dzień na stos.

Sprawdzać trzeba tylko wierzchołek stosu. Dzień jest dodawany na stos dopiero po zdjęciu z niego wszystkich chłodniejszych dni znajdujących się nad nim, więc temperatury na stosie nigdy nie rosną od dołu do góry. Jeśli dzisiaj nie jest cieplej niż w dniu na wierzchołku, nie jest też cieplej niż w żadnym dniu poniżej, więc przestajesz zdejmować elementy ze stosu. W pierwszym przykładzie dzień 5 (75) zdejmuje dni 4, 3 i 2, z czasem oczekiwania wynoszącym odpowiednio 1, 2 i 3, podczas gdy drugie 70 nigdy nie zdejmuje pierwszego, ponieważ równa temperatura nie jest cieplejsza.

Każdy dzień jest dodawany na stos raz i zdejmowany z niego co najwyżej raz, więc łączna liczba zdjęć wynosi co najwyżej n: czas O(n), nawet jeśli jednego dnia można zdjąć wiele elementów.

Algorytm

Utwórz tablicę odpowiedzi wypełnioną zerami oraz 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 today minus jego indeks.
Umieść today na stosie.
Po zakończeniu pętli dni pozostałe na stosie nie mają cieplejszego dnia i zachowują wartość 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

Zdejmowanie elementów przy >= zamiast >. W pierwszym przykładzie dzień 3 czeka wtedy 1 dzień na drugą temperaturę 70 zamiast 2 dni na 75.
Dodawanie temperatur zamiast indeksów. Nie możesz wtedy obliczyć odległości ani określić, który element odpowiedzi uzupełnić.
Używanie if, gdy potrzebujesz while. Jeden ciepły dzień może odpowiadać na wiele oczekujących dni: w pierwszym przykładzie 75 odpowiada na trzy.
Pozostawianie dni nadal znajdujących się na stosie bez ustawionej wartości. Ich odpowiedź to 0; w C przydziel pamięć na odpowiedź za pomocą calloc, ponieważ pamięć z malloc zawiera śmieci.
Kontynuowanie skanowania do przodu poza pierwszym cieplejszym dniem. Bez break zostanie zapisany ostatni cieplejszy dzień.

Najczęstsze pytania3

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

Rozwiązanie z użyciem stosu monotonicznego działa w czasie O(n) i wymaga O(n) dodatkowej pamięci, ponieważ każdy dzień jest dodawany na stos raz i zdejmowany z niego najwyżej raz. Przeszukiwanie 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.

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

Tak. Wypełniaj odpowiedzi, cofając się od ostatniego dnia, a dla dnia i zacznij od j = i+1; dopóki dzień j nie jest cieplejszy, przejdź do j + answer[j], czyli dnia, który odpowiada na pytanie dla j. Jeśli answer[j] wynosi 0, dzień i również otrzymuje 0. Przeskoki pomijają dni, które nie mogą odpowiedzieć na pytanie dla i: czas O(n), bez dodatkowej pamięci.

Jaki związek mają Daily Temperatures i Next Greater Element?

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

def dailyTemperatures(temperatures):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

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

Oczekiwany wynik

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