Trapping Rain Water
Una fila di barre è affiancata, ciascuna larga un’unità: height[i] è l’altezza della barra i. La pioggia cade sulla fila e si raccoglie negli avvallamenti tra le barre. L’acqua resta sopra una barra solo se a sinistra e a destra si trova una barra più alta; oltre la prima e l’ultima barra scorre via.
Restituisci il numero totale di quadrati unitari d’acqua contenuti nella fila.
Funzione
- heightinteger-array
- l’altezza di ciascuna barra, da sinistra a destra
- Restituisceinteger
- le unità totali di acqua intrappolata
Vincoli
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- Ogni barra è larga un'unità e l'acqua non rimane oltre la prima o l'ultima barra.
Esempi
- Input
- height = [0, 3, 1, 0, 2, 5, 1, 2]
- Output
- 7
- Spiegazione
- Tra il 3 e il 5 l’acqua sale fino al livello 3: contiene 2 unità sopra la barra di 1, 3 sopra lo 0 e 1 sopra il 2. L’1 vicino alla fine si trova tra il 5 e un 2, quindi il suo livello è 2 e contiene 1 unità. 2 + 3 + 1 + 1 = 7.
- Input
- height = [4, 1, 3, 0, 5]
- Output
- 8
- Spiegazione
- La parete più bassa è il 4 a sinistra, quindi l’intera depressione si riempie fino al livello 4: 3 unità sopra l’1, 1 sopra il 3 e 4 sopra lo 0, per un totale di 8. Il 5 a destra non alza il livello, perché l’acqua traboccherebbe prima dal 4.
- Input
- height = [1, 2, 4, 2, 1]
- Output
- 0
- Spiegazione
- Le barre salgono fino a 4 e poi scendono di nuovo. Ogni barra ha un lato oltre il quale non c’è nulla di più alto, quindi l’acqua defluisce e la risposta è 0.
+17 test nascosti all’invio
Per approfondire
Supponiamo che le barre formino una griglia 2D di altezze e che l’acqua possa fuoriuscire in tutte e quattro le direzioni. Come conteresti l’acqua intrappolata in questo caso?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Dimentica l’intera riga e guarda una barra. Quanto può salire l’acqua sopra la barra
ie quali barre determinano quell’altezza?Il livello dell'acqua sopra la barra
iè il minore tra due numeri: la barra più alta dall'inizio fino aie la barra più alta daifino alla fine. La barraitrattiene quel livello meno la propria altezza. Entrambi i massimi progressivi possono essere calcolati con una sola passata da ciascuna estremità.Ti serve solo il minore dei due massimi. Posiziona un puntatore a ciascuna estremità e tieni traccia della barra più alta incontrata da ciascun puntatore. Il livello dell’acqua in corrispondenza del puntatore sulla barra più bassa è determinato dal suo massimo corrente: aggiungi quell’acqua e sposta il puntatore verso l’interno. Fermati quando i puntatori si incontrano.
Soluzione
L’acqua sopra ogni barra dipende da barre che possono trovarsi molto lontano, su entrambi i lati, quindi uno sguardo locale ai vicini porta a un risultato errato. La soluzione è una formula: il livello sopra una barra è il minore tra la barra più alta alla sua sinistra e la barra più alta alla sua destra. Cercare questi due massimi partendo da ogni barra è lento; memorizzarli in due array rende l’algoritmo lineare, mentre due puntatori che si spostano sempre dal lato più basso non richiedono affatto array.
Scansiona entrambi i lati di ogni misura
Corretto, ma non termina sui test più grandi
Intuizione
Calcola l’acqua colonna per colonna. L’acqua sopra la barra i sale finché non traboccherebbe dalla parete più bassa delle due. La parete sinistra è la barra più alta in assoluto dall’indice 0 a i; la parete destra è la barra più alta da i fino alla fine. Quindi il livello è min(leftMax, rightMax) e l’acqua sopra la barra i è quel livello meno height[i].
Prendi [0, 3, 1, 0, 2, 5, 1, 2] e la barra di altezza 0 all’indice 3. La barra più alta alla sua sinistra è 3, mentre a destra è 5. Il livello è 3, quindi lì si accumulano 3 unità. Per la barra di altezza 1 all’indice 6, le pareti sono 5 e 2: il livello è 2 e trattiene 1 unità.
Entrambe le scansioni includono la barra i. In questo modo il risultato non diventa negativo: quando la barra i è più alta di tutte le altre su un lato, il massimo di quel lato è la sua stessa altezza, il livello è uguale alla sua altezza e trattiene 0 unità. È anche per questo che la prima e l’ultima barra trattengono sempre 0 unità.
Il problema è il costo. Per ogni barra si esamina l’intera riga, metà a sinistra e metà a destra, quindi il totale è n × n letture: 4 × 10^8 per 2 × 10^4 barre. Inoltre, le scansioni ripetono il lavoro: la barra più alta a sinistra dell’indice 5 è la barra più alta a sinistra dell’indice 4, più un confronto; la forza bruta la ricalcola da zero.
Algoritmo
- Imposta
watersu 0. - Per ogni indice
i, esegui una scansione da 0 aiper trovareleftMax. - Esegui una scansione da
iall'ultimo indice per trovarerightMax. - Aggiungi
min(leftMax, rightMax) - height[i]awater. - Restituisci
water.
def trap(height):
n = len(height)
water = 0
for i in range(n):
# The tallest bar at or left of i, and the tallest at or right of i.
left_max = 0
for j in range(i + 1):
left_max = max(left_max, height[j])
right_max = 0
for j in range(i, n):
right_max = max(right_max, height[j])
water += min(left_max, right_max) - height[i]
return waterPrecalcola la barra più alta su ciascun lato
Intuizione
La formula rimane invariata; cambia solo il modo in cui trovi le due pareti. La barra più alta da 0 a i è la più alta tra la barra più alta da 0 a i-1 e height[i]. Quindi, una passata da sinistra a destra riempie un array leftMax, costruendo ogni elemento a partire da quello precedente. Una passata da destra a sinistra riempie rightMax allo stesso modo. Una terza passata somma min(leftMax[i], rightMax[i]) - height[i] per ogni barra.
Per [0, 3, 1, 0, 2, 5, 1, 2]: leftMax = [0, 3, 3, 3, 3, 5, 5, 5] e rightMax = [5, 5, 5, 5, 5, 5, 2, 2]. I valori minori tra i due array sono i livelli [0, 3, 3, 3, 3, 5, 2, 2]. Sottrai le altezze e ottieni [0, 0, 2, 3, 1, 0, 1, 0], la cui somma è 7.
Ogni passata visita ogni barra una volta, quindi il tempo è O(n): circa 6 × 10^4 passaggi per 2 × 10^4 barre invece di 4 × 10^8. Il prezzo da pagare è l'uso di due array aggiuntivi di n numeri. Questa è la versione da scegliere per prima in un colloquio: è difficile sbagliare e l'approccio successivo serve a eliminare gli array, non introduce un'idea diversa.
Algoritmo
- Riempi
leftMaxda sinistra a destra:leftMax[0] = height[0], poileftMax[i] = max(leftMax[i-1], height[i]). - Riempi
rightMaxda destra a sinistra:rightMax[n-1] = height[n-1], poirightMax[i] = max(rightMax[i+1], height[i]). - Per ogni indice, aggiungi
min(leftMax[i], rightMax[i]) - height[i]al totale. - Restituisci il totale.
def trap(height):
n = len(height)
left_max = [0] * n # tallest bar from index 0 to i
right_max = [0] * n # tallest bar from index i to n-1
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - height[i]
return waterDue puntatori che spostano il lato inferiore
Intuizione
La formula ha bisogno solo della più bassa delle due pareti. Se riesci a dimostrare che la parete sinistra è quella più bassa in un certo indice, non hai mai bisogno della parete destra di quell’indice. Due puntatori ti permettono di dimostrarlo. Metti left all’indice 0 e right all’ultimo indice, e mantieni leftMax e rightMax, la barra più alta che ciascun puntatore ha superato finora, compresa la barra su cui si trova.
L’invariante: ogni barra che i puntatori hanno già superato non è più alta della più alta delle due barre su cui si trovano ora. È vero perché sposti sempre il puntatore sulla barra più bassa, quindi un puntatore supera solo una barra che non è più alta della barra sotto l’altro puntatore.
Ora supponiamo che height[left] < height[right]. Per l’invariante, leftMax è al massimo pari a height[right], e height[right] è a sua volta una barra alla destra di left. Quindi la vera parete destra di left è alta almeno quanto leftMax, e il livello in corrispondenza di left è esattamente leftMax, qualunque cosa si trovi tra i puntatori. Aggiungi leftMax - height[left] e sposta left di un passo a destra. Quando height[right] è la barra più bassa o di pari altezza, fai la stessa cosa sul lato destro. Aggiorna il massimo corrente prima di aggiungere l’acqua, così la barra sotto il puntatore conta come la propria parete e l’acqua non è mai negativa.
Seguiamo [0, 3, 1, 0, 2, 5, 1, 2]. I puntatori iniziano su 0 e 2: quello a sinistra è più basso e trattiene 0. Poi 3 contro 2: quello a destra è più basso, rightMax diventa 2 e trattiene 0. Poi 3 contro 1: quello a destra è di nuovo più basso, l’1 trattiene 2-1 = 1. Poi 3 contro 5: ora quello a sinistra è più basso, leftMax è 3; il 3 trattiene 0, l’1 trattiene 2, lo 0 trattiene 3 e il 2 trattiene 1. I puntatori si incontrano sul 5. Il totale è 1 + 2 + 3 + 1 = 7, con un’unica scansione e quattro variabili.
Algoritmo
- Imposta
left = 0,right = n-1e impostaleftMax,rightMaxewatera 0. - Mentre
left < right, confrontaheight[left]conheight[right]. - Se la barra a sinistra è più bassa, aumenta
leftMaxaheight[left]se necessario, aggiungileftMax - height[left]e spostalefta destra. - Altrimenti aumenta
rightMaxaheight[right]se necessario, aggiungirightMax - height[right]e spostarighta sinistra. - Restituisci
waterquando i puntatori si incontrano; la barra su cui si incontrano è la più alta e non trattiene acqua.
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = 0 # tallest bar passed so far from each end
water = 0
while left < right:
if height[left] < height[right]:
# A bar taller than height[left] waits on the right, so left_max sets the level here.
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
# A bar at least as tall as height[right] waits on the left, so right_max sets the level.
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
Trappole e casi limite
La formula è breve e la maggior parte delle risposte errate dipende dall’ordine di due righe o dal lato verso cui ci si sposta.
- Aggiungere l’acqua prima di aggiornare il massimo corrente. Se
height[left]è maggiore dileftMax,leftMax - height[left]è negativo e il totale diminuisce. Aggiorna prima il massimo, poi aggiungi. - Spostare il puntatore sulla barra più alta. Il livello è noto solo sul lato più basso; spostarsi dal lato più alto significa usare una parete che non hai dimostrato. Su
[4, 1, 3, 0, 5]questa versione restituisce 4 invece di 8. - Considerare solo i vicini più prossimi. Le pareti di una barra possono essere lontane: in
[3, 0, 2, 0, 1, 0, 4]la barra di 1 trattiene acqua fino al livello 3, determinato da barre che si trovano a quattro e due passi di distanza. La risposta è 12. - Considerare le estremità dell’array come pareti. L’acqua oltre la prima o l’ultima barra defluisce, quindi una sola barra, due barre o una sequenza che sale soltanto o scende soltanto trattiene 0.
- Escludere la barra
idalle sue scansioni nel metodo a forza bruta. In tal caso una barra più alta di entrambi i lati ottiene una quantità negativa. Includila oppure limita il risultato a 0. - Overflow in una variante che moltiplica. Qui la risposta arriva a circa 2 × 10^9 (due barre di 10^5 attorno a 19,998 celle vuote), valore che rientra comunque in un intero con segno a 32 bit; nelle tue varianti, usa somme a 64 bit.
Domande frequenti4
Qual è la complessità temporale di Trapping Rain Water?
La soluzione con due puntatori ha complessità temporale O(n) e usa O(1) spazio aggiuntivo: a ogni passaggio, un puntatore si sposta verso l'interno, quindi ci sono n-1 passaggi. La versione con gli array leftMax e rightMax ha anch'essa complessità temporale O(n), ma usa O(n) spazio. Scansionare entrambi i lati da ogni barra ha complessità O(n²), circa 4 × 10^8 letture per 2 × 10^4 barre.
Perché la soluzione con due puntatori può spostare il lato più corto?
Ogni barra già superata non è più alta della più alta delle due barre attuali, perché si sposta solo il puntatore più basso. Quindi, quando la barra a sinistra è più bassa, il suo massimo progressivo è al massimo pari alla barra a destra, e la barra a destra è una parete reale alla sua destra. Il livello al puntatore sinistro è il suo massimo progressivo, indipendentemente da ciò che si trova tra i puntatori, e puoi sistemare quella barra e proseguire.
Si può risolvere Trapping Rain Water con uno stack?
Sì. Mantieni uno stack di indici le cui altezze diminuiscono dal basso verso l’alto. Quando arriva una barra più alta di quella in cima, rimuovi la cima: è il fondo di una vasca le cui pareti sono la nuova cima dello stack e la barra corrente. Aggiungi (min(two walls) - floor) × (distance between the walls - 1) e continua a rimuovere elementi finché la barra corrente è più alta. Lo stack riempie l’acqua in strati orizzontali anziché in colonne, in O(n) di tempo e O(n) di spazio.
In che cosa Trapping Rain Water è diverso da Container With Most Water?
In Container With Most Water scegli due linee e quelle comprese tra loro non occupano spazio, quindi la risposta è un unico rettangolo, il più grande. Qui ogni barra è piena, l’acqua si trova sopra ogni barra e la risposta è la somma di tutte le barre. Entrambi gli approcci usano due puntatori che spostano il lato più basso, per lo stesso motivo: il risultato del lato più basso è già determinato.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def trap(height):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
height = [0, 3, 1, 0, 2, 5, 1, 2]
Atteso
7