Daily Temperatures

Q: Qual è la complessità temporale di Daily Temperatures?

La soluzione con pila monotona richiede tempo O(n) e spazio aggiuntivo O(n) . Ogni giorno viene inserito una volta e rimosso al massimo una volta, quindi il ciclo interno viene eseguito al massimo n volte nell'intera scansione. Scorrere in avanti da ogni giorno richiede tempo O(n²) , circa 5 × 10^7 confronti per 10^4 giorni senza giornate più calde.

Q: Perché lo stack memorizza gli indici invece delle temperature?

La risposta per un giorno è una distanza, today - day , quindi ti serve la posizione del giorno. L’indice ti dice anche quale elemento dell’array delle risposte riempire quando il giorno viene estratto. La temperatura si ottiene con un solo accesso tramite temperatures[day] , quindi memorizzarla non aggiunge nulla.

Q: È possibile risolvere Daily Temperatures senza uno stack?

Sì. Procedi dall'ultimo giorno al primo e, per il giorno i , inizia da j = i+1 . Finché il giorno j non è più caldo, salta al giorno che fornisce la risposta per j , j + answer[j] ; se answer[j] è 0, non esiste alcun giorno più caldo e anche al giorno i viene assegnato 0. I salti ignorano ogni giorno che non può essere la risposta, ogni giorno viene saltato al massimo una volta e il tempo rimane O(n) , senza usare memoria oltre all'array delle risposte.

MedioStack monotono

+10

Ottieni la temperatura di ogni giorno in una sequenza di giorni: temperatures[i] è la temperatura del giorno i. Per ogni giorno, conta quanti giorni devi aspettare dopo di esso prima che arrivi un giorno più caldo. Se in seguito non arriva alcun giorno più caldo, l'attesa per quel giorno è 0.

Restituisci un array della stessa lunghezza in cui l'elemento i è l'attesa per il giorno i.

Funzione

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

temperaturesinteger-array: la temperatura di ogni giorno, in ordine
Restituisceinteger-array: per ogni giorno, il numero di giorni che mancano a un giorno più caldo, oppure 0 se non ce n’è nessuno

Vincoli

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
Più caldo significa strettamente più alto: un giorno successivo con la stessa temperatura non conta.

Esempi

Input: temperatures = [71, 69, 72, 70, 70, 75, 68]
Output: [2, 1, 3, 2, 1, 0, 0]
Spiegazione: Il giorno 0 è 71 e il primo giorno più caldo è il giorno 2, a 72, quindi aspetta 2 giorni. I giorni 3 e 4 sono entrambi a 70: il secondo 70 non è più caldo, quindi il giorno 3 aspetta fino al giorno 5, a 75, cioè 2 giorni. Dopo 75 o 68 non c’è nulla di più caldo, quindi entrambi ottengono 0.

+13 test nascosti all’invio

Per approfondire

Le temperature assumono solo 71 valori, da 30 a 100. In che modo una tabella indicizzata per temperatura potrebbe rispondere ogni giorno in un'unica passata da destra a sinistra, e quanto costa questa passata?

Soluzione

Per un singolo giorno, la risposta è una scansione in avanti, ma ripetere la scansione per ogni giorno ripete lo stesso lavoro e, quando le giornate calde sono rare, ogni scansione arriva fino alla fine dell'array. La soluzione è far sì che ogni giorno dia una risposta ai giorni precedenti, invece di chiedere informazioni su quelli successivi: una pila di indici ancora in attesa, ordinata in base alla temperatura, fornisce tutte le risposte in un unico passaggio.

Scansiona in avanti da ogni giorno

Corretto, ma non termina sui test più grandi

Intuizione

Fai ciò che dice la domanda. Per il giorno i, guarda il giorno i+1, poi i+2 e così via, e fermati al primo giorno con una temperatura strettamente più alta. La distanza j-i è la risposta. Se arrivi alla fine senza trovarne uno, la risposta resta 0.

È corretto perché la scansione visita i giorni successivi in ordine, quindi il primo giorno più caldo che incontra è il primo giorno più caldo che esista. Fermarsi proprio lì è importante: una scansione che continuasse registrerebbe invece l'ultimo giorno più caldo.

È lento quando i giorni più caldi sono lontani o non ce ne sono. Se tutti i 10^4 giorni hanno la stessa temperatura, nessuna scansione si ferma in anticipo: il giorno 0 controlla 9,999 giorni, il giorno 1 ne controlla 9,998 e il totale è circa n²/2 = 5 × 10^7 confronti. Le scansioni si sovrappongono anche: il giorno 1 percorre quasi esattamente il tratto già percorso dal giorno 0 e non ne ricava nulla.

Algoritmo

Crea un array di risposte composto da zeri, una voce per ogni giorno.
Per ogni giorno i, esamina j da i+1 fino all'ultimo giorno.
Al primo j per cui temperatures[j] > temperatures[i], memorizza j-i e interrompi la scansione.
Restituisci l'array di risposte; i giorni per i quali la scansione non ha trovato nulla mantengono 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

Pila monotona dei giorni di attesa

Intuizione

Capovolgi la domanda. Invece di chiederti ogni giorno quale giorno viene dopo, scorri una volta i giorni e lascia che ogni nuovo giorno risponda per i giorni precedenti che supera. Tieni su uno stack, come indici, i giorni che non hanno ancora una risposta. Quando arriva il giorno di oggi, ogni giorno in attesa più freddo di oggi ha trovato il suo primo giorno più caldo: oggi. Estraili tutti e scrivi today - day come risposta. Poi inserisci oggi, che ora aspetta il proprio giorno più caldo.

Scorri [71, 69, 72, 70, 70, 75, 68]. Il giorno 0 (71) viene inserito. Il giorno 1 (69) non è più caldo di 71, quindi viene inserito in cima: lo stack contiene i giorni [0, 1]. Il giorno 2 (72) estrae il giorno 1 (attesa 1) e poi il giorno 0 (attesa 2), quindi viene inserito. I giorni 3 e 4 (70 e 70) vengono inseriti; il secondo 70 non estrae il primo, perché un valore uguale non è più caldo. Il giorno 5 (75) estrae il giorno 4 (attesa 1), il giorno 3 (attesa 2) e il giorno 2 (attesa 3). Il giorno 6 (68) viene inserito. I giorni 5 e 6 sono ancora in attesa alla fine, quindi mantengono 0. La risposta è [2, 1, 3, 2, 1, 0, 0].

Perché conta solo la cima: le temperature nello stack non aumentano dal basso verso l’alto. Un giorno viene inserito solo dopo che tutti i giorni più freddi sopra di esso sono stati estratti, quindi tutto ciò che si trova sotto è almeno altrettanto caldo. Se oggi non è più caldo del giorno in cima, non è più caldo nemmeno di quelli sottostanti, e puoi smettere di estrarre. Un giorno lascia lo stack non appena compare il primo giorno più caldo, quindi l’attesa che registri è fino al primo giorno più caldo, non fino a quello più caldo in assoluto.

Lo stack contiene indici, non temperature, perché la risposta è una distanza e perché devi sapere quale voce della risposta compilare. Recupera la temperatura con temperatures[day]. Ogni giorno viene inserito una volta ed estratto al massimo una volta, quindi tutte le estrazioni nell’intero percorso ammontano al massimo a n, e il tempo totale è O(n), anche se un singolo giorno può causare molte estrazioni.

Algoritmo

Crea un array di risposte composto da zeri e una pila vuota di indici.
Per ogni giorno today, finché il giorno in cima alla pila è più freddo di oggi, rimuovilo e imposta la sua risposta su today meno il suo indice.
Aggiungi today alla pila.
Dopo il ciclo, i giorni ancora nella pila non hanno un giorno più caldo e mantengono 0. Restituisci l'array di risposte.

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

Trappole e casi limite

Il ciclo dello stack è composto da poche righe; i bug si nascondono nel confronto e in ciò che contiene lo stack.

Eseguire il pop con >= invece di >. Un giorno con la stessa temperatura non è più caldo. In [71, 69, 72, 70, 70, 75, 68], il giorno 3 aspetta 2 giorni per arrivare a 75, non 1 giorno per il secondo 70.
Inserire le temperature invece degli indici. La risposta è una distanza in giorni e ti serve l'indice per calcolarla e per sapere quale elemento riempire.
Usare if quando serve while. Una giornata calda può fornire la risposta per molti giorni di attesa contemporaneamente: nel primo esempio, 75 risponde per tre giorni.
Restituire la temperatura più calda o l'indice del giorno più caldo. L'output indica quanti giorni devi aspettare, j-i.
Lasciare non impostate le giornate ancora sullo stack. La loro risposta è 0; in C, alloca la risposta con calloc oppure riempila, perché la memoria di malloc contiene dati spazzatura.
Lasciare che la scansione in avanti prosegua oltre il primo giorno più caldo. Senza il break, registra l'ultimo giorno più caldo invece del primo.

Domande frequenti4

Qual è la complessità temporale di Daily Temperatures?

La soluzione con pila monotona richiede tempo O(n) e spazio aggiuntivo O(n). Ogni giorno viene inserito una volta e rimosso al massimo una volta, quindi il ciclo interno viene eseguito al massimo n volte nell'intera scansione. Scorrere in avanti da ogni giorno richiede tempo O(n²), circa 5 × 10^7 confronti per 10^4 giorni senza giornate più calde.

Perché lo stack memorizza gli indici invece delle temperature?

La risposta per un giorno è una distanza, today - day, quindi ti serve la posizione del giorno. L’indice ti dice anche quale elemento dell’array delle risposte riempire quando il giorno viene estratto. La temperatura si ottiene con un solo accesso tramite temperatures[day], quindi memorizzarla non aggiunge nulla.

È possibile risolvere Daily Temperatures senza uno stack?

Sì. Procedi dall'ultimo giorno al primo e, per il giorno i, inizia da j = i+1. Finché il giorno j non è più caldo, salta al giorno che fornisce la risposta per j, j + answer[j]; se answer[j] è 0, non esiste alcun giorno più caldo e anche al giorno i viene assegnato 0. I salti ignorano ogni giorno che non può essere la risposta, ogni giorno viene saltato al massimo una volta e il tempo rimane O(n), senza usare memoria oltre all'array delle risposte.

In che modo Daily Temperatures è correlato a Next Greater Element?

È la stessa domanda posta per ogni posizione: trova il valore successivo più grande a destra. Next Greater Element restituisce quel valore; Daily Temperatures restituisce quanto dista, ed è per questo che lo stack contiene gli indici. Lo stesso stack monotono, invertito in modo da estrarre gli elementi quando trova un valore più piccolo, risponde anche alle domande sul successivo elemento più piccolo.

Python

def dailyTemperatures(temperatures):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

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