Trapping Rain Water
Una fila di barre è affiancata, ciascuna larga un’unità: height[i] è l’altezza della barra i. La pioggia si raccoglie negli avvallamenti tra le barre. L’acqua rimane sopra una barra solo se da qualche parte alla sua sinistra e alla sua destra c’è una barra più alta; oltre la prima e l’ultima barra, l’acqua defluisce. Restituisci il numero totale di unità d’acqua trattenute dalla fila.
Funzione
- heightinteger-array
- l'altezza di ogni 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 il livello è 3: 2 unità sopra l’1, 3 sopra lo 0, 1 sopra il 2. L’1 successivo si trova tra il 5 e un 2, quindi vale 1. Il totale è 7.
- Input
- height = [4, 1, 3, 0, 5]
- Output
- 8
- Spiegazione
- La parete più bassa è il 4, quindi l'avvallamento si riempie fino al livello 4: 3 unità sopra l'1, 1 sopra il 3, 4 sopra lo 0, per un totale di 8. L'acqua trabocca oltre il 4 prima che il 5 conti.
- 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.
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 barraicontiene quel livello meno la propria altezza. Entrambi i massimi progressivi possono essere calcolati in un'unica passata da ciascuna estremità.Ti serve solo il minore dei due massimi. Metti un puntatore a ciascuna estremità e tieni traccia della barra più alta superata da ciascun puntatore. Il livello dell’acqua in corrispondenza del puntatore sulla barra più bassa è determinato dal massimo raggiunto fino a quel momento da quel puntatore: aggiungi quell’acqua e sposta il puntatore verso l’interno. Fermati quando i puntatori si incontrano.
Soluzione
L’acqua sopra una barra dipende dalle barre che possono essere molto lontane, da entrambi i lati. Il suo livello è il minore tra la barra più alta alla sua sinistra e quella più alta alla sua destra, e la barra trattiene quel livello meno la propria altezza. Gli approcci differiscono solo per il modo in cui trovano quei due massimi.
Scansiona entrambi i lati da ogni battuta
Corretto, ma non termina sui test più grandi
Intuizione
Per ogni barra i, scorri da 0 a i per trovare la barra più alta a sinistra e da i alla fine per trovare quella più alta a destra, quindi aggiungi min(leftMax, rightMax) - height[i]. Includere la barra i in entrambe le scansioni evita che la quantità diventi negativa e assegna 0 alle barre alle estremità.
Ogni barra legge l'intera riga: n = 2 × 10^4 significa 4 × 10^8 letture, la maggior parte delle quali ripete la scansione della barra precedente.
Algoritmo
- Imposta
watersu 0. - Per ogni indice
i, esegui una scansione da 0 aiper trovareleftMax. - Esegui una scansione da
ifino all'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 barra più alta da 0 a i è la maggiore tra la barra più alta da 0 a i-1 e height[i]. Quindi, una passata da sinistra riempie leftMax, costruendo ogni voce a partire da quella precedente, e una passata da destra riempie rightMax. Una terza passata applica la formula.
Per [0, 3, 1, 0, 2, 5, 1, 2], i livelli min(leftMax[i], rightMax[i]) sono [0, 3, 3, 3, 3, 5, 2, 2]. Sottraendo le altezze si ottiene [0, 0, 2, 3, 1, 0, 1, 0], la cui somma è 7. Il tempo di esecuzione è O(n), al prezzo di due array di n numeri.
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 del muro più basso, e due puntatori possono dimostrare quale sia. Imposta left a 0 e right all’ultimo indice, tieni traccia di leftMax e rightMax, la barra più alta superata da ciascun puntatore, inclusa quella su cui si trova, e sposta sempre il puntatore sulla barra più bassa. Allora ogni barra già superata non è più alta della più alta delle due barre correnti, perché un puntatore supera solo una barra non più alta di quella sotto l’altro puntatore.
Supponiamo che height[left] < height[right]. Per l’invariante, leftMax è al massimo height[right], una barra a destra di left. Quindi il muro destro di left è alto almeno leftMax e il suo livello è esattamente leftMax, qualunque cosa si trovi tra i puntatori. Quando la barra di destra è più bassa o uguale, il ragionamento speculare determina right.
Algoritmo
- Imposta
left = 0,right = n-1e impostaleftMax,rightMaxewatera 0. - Mentre
left < right: seheight[left] < height[right], aumentaleftMaxfino aheight[left]se necessario, aggiungileftMax - height[left]e spostaleftverso destra. - Altrimenti fai lo stesso sul lato destro e sposta
rightverso sinistra. - Restituisci
water. La barra in cui si incontrano i puntatori è 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
- Aggiungere l’acqua prima di aggiornare il massimo progressivo. Quando
height[left]è maggiore dileftMax, la quantità è negativa e il totale diminuisce. - Spostare il puntatore sulla barra più alta, il cui livello non è dimostrato. Su
[4, 1, 3, 0, 5]questa versione restituisce 4 invece di 8. - Considerare solo le barre adiacenti. In
[3, 0, 2, 0, 1, 0, 4]la barra di 1 si riempie fino al livello 3, determinato da barre distanti rispettivamente quattro e due posizioni; la risposta è 12. - Considerare le estremità dell’array come pareti. L’acqua fuoriesce da lì, quindi una barra, due barre o una fila che sale soltanto o scende soltanto trattiene 0.
Domande frequenti3
Qual è la complessità temporale del problema dell’acqua piovana intrappolata?
La soluzione con due puntatori richiede un tempo O(n) e uno spazio aggiuntivo O(1), poiché a ogni passaggio un puntatore si sposta verso l'interno. La versione con gli array leftMax e rightMax richiede anch'essa un tempo O(n), ma usa uno spazio O(n). Scansionare entrambi i lati da ogni barra richiede O(n²).
È possibile risolvere Trapping Rain Water con una pila?
Sì. Mantieni uno stack di indici con altezze decrescenti. Quando arriva una barra più alta, rimuovi l’elemento in cima: è il fondo di una vasca delimitata dalla nuova cima e dalla barra corrente. Aggiungi (min(two walls) - floor) × (distance between the walls - 1) e continua a rimuovere elementi. In questo modo l’acqua viene riempita a strati orizzontali, in O(n) tempo e spazio.
In che cosa Trapping Rain Water è diverso da Container With Most Water?
In Container With Most Water le linee non occupano spazio e la risposta è il singolo rettangolo più grande tra due linee. Qui ogni barra è piena e la risposta somma l'acqua sopra tutte le barre. In entrambi i casi si sposta il lato più basso per lo stesso motivo: il suo risultato è già determinato.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def trap(height):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
height = [0, 3, 1, 0, 2, 5, 1, 2]
Output atteso
7