Trapping Rain Water: stack e due puntatori
Risolva trapping-rain-water usando sia l'approccio con stack monotono, che calcola gli strati orizzontali, sia l'approccio a due puntatori, che calcola le colonne verticali.
Trapping Rain Water: stack e due puntatori è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Problema: intrappolamento dell'acqua piovana
Trapping Rain Water (LeetCode 42) è uno dei problemi più iconici dei colloqui tecnici. Dato un array di n interi non negativi che rappresentano una mappa delle elevazioni, in cui ogni barra ha larghezza 1, calcoli quanta acqua può rimanere intrappolata tra le barre dopo la pioggia. L'acqua si accumula in ogni avvallamento tra barre più alte su entrambi i lati.
Per ogni posizione i, il livello dell'acqua è min(max_left[i], max_right[i]) - height[i]. Se il risultato è negativo, non rimane acqua (la barra è più alta di almeno uno dei due confini). Esistono tre approcci: array dei massimi precalcolati O(n)/O(n), due puntatori O(n)/O(1) e stack monotono O(n)/O(n).
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
# Water trapped at each position:
# pos 2: min(1,3)-0=1
# pos 4: min(2,3)-1=1
# pos 5: min(2,3)-0=2
# pos 6: min(2,3)-1=1
# pos 9: min(3,2)-1=1
# Total = 6
print('height:', height)
print('Expected trapped water: 6')
# Visualise
max_h = max(height)
for row in range(max_h, 0, -1):
line = ''
for h in height:
line += '#' if h >= row else ' '
print(line)Approccio 1: array dei massimi precalcolati
La soluzione diretta, con tempo O(n) e spazio O(n), precalcola due array: max_left[i] = altezza massima dall'indice 0 a i e max_right[i] = altezza massima dall'indice i a n-1. L'acqua nella posizione i è max(0, min(max_left[i], max_right[i]) - height[i]).
La costruzione di max_left richiede un'unica scansione da sinistra a destra; max_right richiede una scansione da destra a sinistra. Un'ultima scansione somma l'acqua. Questo approccio è chiaro e facile da spiegare, ma utilizza O(n) di spazio aggiuntivo.
def trap_prefix(height):
n = len(height)
if n < 3:
return 0
max_left = [0] * n
max_right = [0] * n
max_left[0] = height[0]
for i in range(1, n):
max_left[i] = max(max_left[i-1], height[i])
max_right[-1] = height[-1]
for i in range(n-2, -1, -1):
max_right[i] = max(max_right[i+1], height[i])
water = 0
for i in range(n):
water += max(0, min(max_left[i], max_right[i]) - height[i])
return water
print(trap_prefix([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_prefix([4,2,0,3,2,5])) # 9Approccio 2: due puntatori (spazio O(1))
L'approccio a due puntatori raggiunge un tempo O(n) e uno spazio O(1). Utilizzi i puntatori left e right, inizialmente alle due estremità. Mantenga max_left e max_right come massimi progressivi osservati finora da ciascun lato.
A ogni passaggio, elabori il lato con il massimo progressivo più piccolo, perché quel lato è il fattore limitante. Se max_left < max_right, l'acqua in corrispondenza del puntatore sinistro è max_left - height[left] (il lato destro è sufficientemente alto). Sposti il puntatore sinistro verso il centro. In caso contrario, elabori simmetricamente il puntatore destro. Non servono array precalcolati.
def trap_two_pointer(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left] # new max on the left
else:
water += max_left - height[left] # trapped by max_left
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap_two_pointer([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_two_pointer([4,2,0,3,2,5])) # 9
print(trap_two_pointer([3,0,3])) # 3Perché funzionano due puntatori: l'invariante
L'idea chiave è questa: quando elaboriamo il puntatore sinistro perché height[left] < height[right], sappiamo che max_right >= height[right] > height[left]. Di conseguenza, il confine effettivo dell'acqua a destra è almeno height[right], che è già maggiore di max_left. Quindi min(max_left, effective_max_right) = max_left e la formula dell'acqua si semplifica in max_left - height[left].
Non è necessario conoscere l'esatto max_right: sapere soltanto che è almeno height[right] > height[left] è sufficiente per utilizzare max_left come livello dell'acqua. Questo è l'elegante invariante che rende possibile lo spazio O(1).
# Trace two-pointer on [4, 2, 0, 3, 2, 5]
height = [4, 2, 0, 3, 2, 5]
left, right = 0, len(height) - 1
max_l = max_r = water = 0
print('height:', height)
print(f'{'Step':5} {'L':3} {'R':3} {'maxL':5} {'maxR':5} {'water':6} {'total':6}')
step = 0
while left < right:
side = 'L' if height[left] < height[right] else 'R'
if side == 'L':
if height[left] >= max_l: max_l = height[left]
else:
w = max_l - height[left]; water += w
left += 1
else:
if height[right] >= max_r: max_r = height[right]
else:
w = max_r - height[right]; water += w
right -= 1
step += 1
print(f'{step:5} {left:3} {right:3} {max_l:5} {max_r:5} {water:6}')
print('Total trapped:', water)Approccio 3: stack monotono (strati orizzontali)
L'approccio con stack monotono calcola l'acqua in strati orizzontali tra barre adiacenti. Mantenga uno stack monotono decrescente di indici. Quando la barra i è più alta dell'elemento in cima allo stack j, si forma una valle: il fondo è height[j], la parete sinistra è height[stack[-1]] dopo aver rimosso j e la parete destra è height[i]. L'acqua riempie la valle fino a min(left_wall, right_wall) - floor, con larghezza i - stack[-1] - 1.
Ogni «valle» viene calcolata quando si incontra una barra più alta. In questo modo l'acqua viene elaborata in segmenti rettangolari delimitati, una caratteristica utile quando è necessario tenere traccia anche delle barre che contribuiscono al livello dell'acqua.
def trap_stack(height):
stack = [] # monotonic decreasing indices
water = 0
for i in range(len(height)):
while stack and height[stack[-1]] < height[i]:
bottom_idx = stack.pop() # the floor of the valley
if not stack:
break # no left wall, no water
left_idx = stack[-1]
floor = height[bottom_idx]
water_height = min(height[left_idx], height[i]) - floor
width = i - left_idx - 1
water += water_height * width
stack.append(i)
return water
print(trap_stack([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_stack([4,2,0,3,2,5])) # 9Tracciamento dello stack monotono
Tracciamo [0,1,0,2,1,0,1,3,...] con l'approccio basato sullo stack. Quando incontriamo la barra 3 (h=2) in i=3, l'elemento in cima allo stack è i=2 (h=0): lo rimuoviamo. La parete sinistra è i=1 (h=1), mentre la parete destra è h=2. Altezza dell'acqua = min(1,2)-0=1, larghezza=3-1-1=1, area=1. Proseguendo, l'elemento in cima allo stack i=1 (h=1) non è minore di 2, quindi ci fermiamo. Inseriamo 3 nello stack.
Il metodo dello stack è più complesso da implementare rispetto a quello a due puntatori, ma mostra quali barre specifiche formano ogni cella d'acqua. Questa informazione è utile nelle domande successive sulla ricostruzione della disposizione dell'acqua o sul conteggio delle valli distinte.
def trap_stack_trace(height):
stack = []
water = 0
for i in range(len(height)):
print(f'i={i} h={height[i]}: stack={[height[s] for s in stack]}')
while stack and height[stack[-1]] < height[i]:
bot = stack.pop()
if not stack:
print(f' Pop {height[bot]}: no left wall, skip')
break
left = stack[-1]
h = min(height[left], height[i]) - height[bot]
w = i - left - 1
water += h * w
print(f' Pop {height[bot]}: floor={height[bot]}, left_wall={height[left]}, right_wall={height[i]}, h={h}, w={w}, +{h*w}')
stack.append(i)
return water
result = trap_stack_trace([0,1,0,2,1,0,1,3,2,1,2,1])
print('Total:', result)Confronto tra i tre approcci
Riepilogo dei tre approcci alla raccolta dell'acqua piovana:
- Array di prefissi: tempo O(n), spazio O(n). Il più facile da comprendere e verificare. Ideale nei colloqui in cui la chiarezza è più importante dell'efficienza dello spazio.
- Due puntatori: tempo O(n), spazio O(1). Ottimale sia in termini di tempo sia di spazio. Ideale per le domande di approfondimento come «è possibile usare spazio O(1)?».
- Stack monotono: tempo O(n), spazio O(n). Elabora l'acqua in strati orizzontali. Ideale quando è necessario sapere quali barre contribuiscono o quando il problema compare come sottoproblema in un algoritmo più ampio basato su stack.
height = [0,1,0,2,1,0,1,3,2,1,2,1]
# All three methods — verify they agree
def trap_prefix(h):
n = len(h)
ml = [0]*n; mr = [0]*n; ml[0]=h[0]; mr[-1]=h[-1]
for i in range(1,n): ml[i]=max(ml[i-1],h[i])
for i in range(n-2,-1,-1): mr[i]=max(mr[i+1],h[i])
return sum(max(0,min(ml[i],mr[i])-h[i]) for i in range(n))
def trap_two_ptr(h):
l,r,ml,mr,w = 0,len(h)-1,0,0,0
while l<r:
if h[l]<h[r]:
ml=max(ml,h[l]); w+=ml-h[l]; l+=1
else:
mr=max(mr,h[r]); w+=mr-h[r]; r-=1
return w
def trap_stk(h):
stk,w = [],[]
for i in range(len(h)):
while stk and h[stk[-1]]<h[i]:
b=stk.pop()
if not stk: break
w.append(max(0,min(h[stk[-1]],h[i])-h[b])*(i-stk[-1]-1))
stk.append(i)
return sum(w)
for h in [height, [4,2,0,3,2,5], [3,0,3], [1,0,1]]:
p=trap_prefix(h); t=trap_two_ptr(h); s=trap_stk(h)
print(f'{h}: prefix={p}, two-ptr={t}, stack={s}, match={p==t==s}')Contenitore con più acqua
Contenitore con più acqua (LeetCode 11) viene spesso confuso con la raccolta dell'acqua piovana. In questo caso si scelgono esattamente due barre e l'acqua è delimitata solo da esse (le barre interne non contano). Massimizzi l'area min(height[l], height[r]) × (r - l).
I due puntatori risolvono il problema con una strategia greedy: si parte dalle due estremità (larghezza massima). Si sposti verso l'interno il puntatore della barra più corta: spostare quello della barra più alta può solo ridurre l'area. Il tempo è O(n) e lo spazio O(1), quindi l'approccio è più semplice rispetto a quello a due puntatori per la raccolta dell'acqua piovana, perché non è necessario mantenere alcun massimo corrente.
def max_water_container(height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)
# Move the shorter bar: moving taller bar can only reduce min
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
print(max_water_container([1,8,6,2,5,4,8,3,7])) # 49: bars 8 and 7
print(max_water_container([1,1])) # 1
print(max_water_container([4,3,2,1,4])) # 16
# Key difference from trapping rain water:
# Container: choose 2 bars, water fills freely between them (no internal barriers)
# Trapping: water fills ALL valleys in the full elevation mapAvanzato: raccolta dell'acqua piovana II (3D)
Raccolta dell'acqua piovana II (LeetCode 407) estende il problema a una matrice di altezze 2D. L'acqua può scorrere in tutte e quattro le direzioni e deve defluire oltre il bordo. La soluzione usa un min-heap: inizializzi l'heap con tutte le celle sul bordo, quindi esegua un'espansione simile a una BFS. Elabori la cella con altezza minore: ogni vicino più basso deve contenere acqua almeno fino al livello della cella corrente.
Si tratta di un algoritmo fondamentalmente diverso da quello del caso 1D, che verifica sia le operazioni sugli heap sia l'attraversamento BFS. La tecnica dei due puntatori per il caso 1D non si generalizza al 2D; l'approccio con heap sì.
import heapq
def trap_rain_water_2d(heightMap):
if not heightMap or not heightMap[0]:
return 0
m, n = len(heightMap), len(heightMap[0])
visited = [[False]*n for _ in range(m)]
heap = [] # (height, row, col)
# Add all border cells to the heap
for i in range(m):
for j in [0, n-1]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
for j in range(n):
for i in [0, m-1]:
if not visited[i][j]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
total = 0
max_h = 0
while heap:
h, r, c = heapq.heappop(heap)
max_h = max(max_h, h)
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0<=nr<m and 0<=nc<n and not visited[nr][nc]:
visited[nr][nc] = True
total += max(0, max_h - heightMap[nr][nc])
heapq.heappush(heap, (max(max_h, heightMap[nr][nc]), nr, nc))
return total
map2d = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
print(trap_rain_water_2d(map2d)) # 4Quando usare ciascun metodo nei colloqui
Guida alla scelta per il colloquio sulla raccolta dell'acqua piovana:
- Inizi da: array di prefissi — facili da spiegare, intuitivi dal punto di vista visivo e chiaramente corretti
- Domanda di approfondimento «spazio O(1)?»: due puntatori — spieghi l'invariante secondo cui il lato più basso costituisce il collo di bottiglia
- Se l'intervistatore chiede «un altro approccio?»: stack monotono — spieghi il calcolo per strati orizzontali
Prima di passare al codice, definisca sempre con chiarezza ciò che determina il livello dell'acqua in ogni posizione, ovvero il minimo tra la barra più alta a sinistra e quella più alta a destra. Questo dimostra la comprensione del problema e rende più facile spiegare la soluzione.
# Quick summary of all three approaches
approaches = [
{
'name': 'Prefix max arrays',
'time': 'O(n)', 'space': 'O(n)',
'description': '3 passes: build max_left, max_right, sum water column-by-column',
},
{
'name': 'Two pointers',
'time': 'O(n)', 'space': 'O(1)',
'description': 'Process smaller side: its max is the limiting wall, no array needed',
},
{
'name': 'Monotonic stack',
'time': 'O(n)', 'space': 'O(n)',
'description': 'Compute water in horizontal layers when a taller bar is encountered',
},
]
for a in approaches:
print(f'{a["name"]} [{a["time"]} / {a["space"]}]')
print(f' {a["description"]}')
print()Casi limite ed errori comuni
Errori comuni nella raccolta dell'acqua piovana:
- Dimenticare min: il livello dell'acqua è
min(max_left, max_right), non soltanto uno dei due valori. Una barra ha bisogno di pareti alte su entrambi i lati. - Acqua negativa: usi
max(0, ...)per limitare a 0 i valori negativi quando l'altezza di una posizione supera il livello dell'acqua. - Posizioni ai bordi: le barre all'estrema sinistra e all'estrema destra non possono mai contenere acqua, perché manca una parete su un lato. L'approccio con array di prefissi gestisce naturalmente questo caso, poiché
max_left[0] = height[0]fa sì che l'acqua sia sempre 0 all'indice 0. - Array vuoti o molto piccoli: restituisca 0 per gli array con meno di 3 elementi.
def trap(height):
n = len(height)
if n < 3:
return 0 # need at least 3 bars to trap anything
left, right = 0, n - 1
max_l = max_r = water = 0
while left < right:
if height[left] <= height[right]:
if height[left] >= max_l:
max_l = height[left]
else:
water += max_l - height[left] # never negative: max_l > height[left]
left += 1
else:
if height[right] >= max_r:
max_r = height[right]
else:
water += max_r - height[right]
right -= 1
return water
# Edge cases
print(trap([])) # 0: empty
print(trap([1])) # 0: single bar
print(trap([1,2])) # 0: two bars
print(trap([3,0,3])) # 3: simple valley
print(trap([3,3,3])) # 0: flat top, no waterVerifica rapida
Metta alla prova la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: la raccolta dell'acqua piovana si risolve trovando il minimo tra le pareti sinistra e destra più alte in corrispondenza di ogni posizione, l'approccio a due puntatori con spazio O(1) funziona perché il massimo corrente del lato più basso è sempre il vincolo determinante e l'approccio con stack monotono calcola l'acqua per strati orizzontali, risultando utile quando viene combinato con altra logica basata su stack. Ora si passa ai concetti di progettazione dei sistemi, a partire dal framework RADIO per risposte strutturate ai colloqui.
Domande Frequenti
La lezione «Trapping Rain Water: stack e due puntatori» è gratuita?
Sì — il testo completo di «Trapping Rain Water: stack e due puntatori» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Trapping Rain Water: stack e due puntatori»?
Risolva trapping-rain-water usando sia l'approccio con stack monotono, che calcola gli strati orizzontali, sia l'approccio a due puntatori, che calcola le colonne verticali. Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Trapping Rain Water: stack e due puntatori»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Stack monotono: crescente e decrescente
- Rettangolo più grande nell'istogramma
- Massimo in una finestra scorrevole con deque monotona
- Trapping Rain Water: stack e due puntatori