Daily Temperatures

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

La soluzione con pila monotona richiede O(n) tempo e O(n) spazio aggiuntivo, perché ogni giorno viene inserito una volta e rimosso al massimo una volta. Scorrere in avanti a partire da ogni giorno richiede O(n²) tempo, circa 5 × 10^7 confronti per 10^4 giorni senza alcun giorno più caldo.

MedioStack monotono

+10

temperatures[i] è la temperatura del giorno i. Per ogni giorno, conta quanti giorni devi aspettare dopo quel giorno prima che arrivi un giorno strettamente più caldo, oppure 0 se in seguito non arriva nessun giorno più caldo. Restituisci un array della stessa lunghezza, in cui la voce i indica 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 uno 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) attende 2 giorni per il 72. Il giorno 3 (70) salta il 70 uguale del giorno 4 e attende 2 giorni per il 75. Dopo il 75 o il 68 non c’è nulla di più caldo, quindi entrambi ottengono 0.

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 unico passaggio da destra a sinistra, e a quale costo?

Soluzione

Una scansione in avanti da ogni giorno ripete il lavoro e, quando le giornate calde sono rare, ogni scansione arriva fino alla fine. Invece, percorri i giorni una sola volta e lascia che ogni nuovo giorno risponda ai giorni precedenti che supera. I giorni ancora in attesa restano su uno stack le cui temperature non aumentano mai dal basso verso l’alto, così ogni risposta arriva in un’unica passata.

Scansiona in avanti da ogni giorno

Corretto, ma non termina sui test più grandi

Intuizione

Per il giorno i, controlla i giorni i+1, i+2 e così via, e fermati al primo giorno strettamente più caldo j. La risposta è j-i, oppure 0 se la scansione raggiunge la fine. Scansionare in ordine fa sì che il primo giorno più caldo che incontri sia il primo che esiste.

Se tutti i 10^4 giorni hanno la stessa temperatura, nessuna scansione si ferma in anticipo: circa n²/2 = 5 × 10^7 confronti, e il giorno 1 percorre quasi lo stesso tratto già percorso dal giorno 0.

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 cui 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

Stack monotono dei giorni di attesa

Intuizione

Conserva in una pila, come indici, i giorni che non hanno ancora una risposta. Quando arriva oggi, estrai tutti i giorni in attesa più freddi di oggi: oggi è il suo primo giorno più caldo, quindi la risposta è today - day. Poi aggiungi oggi.

Devi controllare solo la cima. Un giorno viene aggiunto solo dopo che tutti i giorni più freddi sopra di esso sono stati estratti, quindi le temperature sulla pila non aumentano dal basso verso l’alto. Se oggi non è più caldo della cima, non è più caldo di nessuno dei giorni sottostanti, quindi smetti di estrarre. Nel primo esempio, il giorno 5 (75) estrae i giorni 4, 3 e 2, con attese di 1, 2 e 3, mentre il secondo 70 non ha mai estratto il primo, perché una temperatura uguale non è più calda.

Ogni giorno viene aggiunto una volta ed estratto al massimo una volta, quindi il totale delle estrazioni è al massimo n: tempo O(n), anche se un giorno può causare molte estrazioni.

Algoritmo

Crea un array di risposte composto da zeri e uno stack vuoto di indici.
Per ogni giorno today, finché il giorno in cima allo stack è più freddo di oggi, estrailo dallo stack e imposta la sua risposta su today meno il suo indice.
Aggiungi today allo stack.
Dopo il ciclo, i giorni ancora nello stack non hanno un giorno più caldo e mantengono il valore 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

Rimuovere elementi con >= invece che con >. Nel primo esempio, il giorno 3 aspetta 1 giorno per il secondo 70 invece di 2 giorni per il 75.
Inserire le temperature invece degli indici. In questo modo non puoi calcolare la distanza né capire quale elemento della risposta compilare.
Usare if quando serve while. Una giornata calda può rispondere a molti giorni di attesa: nel primo esempio, il 75 risponde a tre giorni.
Lasciare senza valore le giornate ancora sullo stack. La loro risposta è 0; in C, alloca la risposta con calloc, perché la memoria di malloc contiene valori spazzatura.
Lasciare che la scansione in avanti prosegua oltre la prima giornata più calda. Senza break, registra invece l'ultima giornata più calda.

Domande frequenti3

Qual è la complessità temporale di Daily Temperatures?

La soluzione con pila monotona richiede O(n) tempo e O(n) spazio aggiuntivo, perché ogni giorno viene inserito una volta e rimosso al massimo una volta. Scorrere in avanti a partire da ogni giorno richiede O(n²) tempo, circa 5 × 10^7 confronti per 10^4 giorni senza alcun giorno più caldo.

È possibile risolvere Daily Temperatures senza uno stack?

Sì. Calcola le risposte partendo dall’ultimo giorno e procedendo a ritroso, e per il giorno i inizia da j = i+1; finché il giorno j non è più caldo, salta a j + answer[j], il giorno che risponde per j. Se answer[j] è 0, anche il giorno i ottiene 0. I salti escludono i giorni che non possono rispondere per i: tempo O(n), senza memoria aggiuntiva.

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 è distante, ed è per questo che lo stack contiene gli indici. Lo stesso stack, modificato in modo da estrarre gli elementi quando si incontra un valore più piccolo, risponde alle domande sul successivo elemento più piccolo.

def dailyTemperatures(temperatures):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso

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