Accumulation d’eau de pluie : pile et deux pointeurs
Résolvez trapping-rain-water avec l’approche par pile monotone, qui calcule des couches horizontales, et l’approche par deux pointeurs, qui calcule des colonnes verticales.
Accumulation d’eau de pluie : pile et deux pointeurs est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Problème : rétention d'eau de pluie
Rétention d'eau de pluie (LeetCode 42) est l'un des problèmes d'entretien les plus emblématiques. Étant donné un tableau de n entiers non négatifs représentant une carte d'altitude où chaque barre a une largeur de 1, calculez la quantité d'eau pouvant être retenue entre les barres après la pluie. L'eau s'accumule dans toute cuvette située entre des barres plus hautes des deux côtés.
Pour chaque position i, le niveau d'eau est min(max_left[i], max_right[i]) - height[i]. Si cette valeur est négative, aucune eau n'est retenue (la barre est plus haute qu'au moins l'une des limites). Trois approches existent : tableaux précalculés O(n)/O(n), deux pointeurs O(n)/O(1) et pile monotone 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)Approche 1 : tableaux de maximums précalculés
La solution directe en O(n) en temps et O(n) en espace précalcule deux tableaux : max_left[i] = hauteur maximale de l'indice 0 à i, et max_right[i] = hauteur maximale de l'indice i à n-1. La quantité d'eau à la position i est max(0, min(max_left[i], max_right[i]) - height[i]).
La construction de max_left nécessite un seul parcours de gauche à droite ; celle de max_right nécessite un parcours de droite à gauche. Un dernier parcours additionne l'eau. Cette approche est claire et facile à expliquer, mais utilise un espace supplémentaire en O(n).
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])) # 9Approche 2 : deux pointeurs (espace O(1))
L'approche à deux pointeurs atteint O(n) en temps et O(1) en espace. Utilisez des pointeurs gauche et droit partant des deux extrémités. Maintenez max_left et max_right comme maximums courants observés jusqu'à présent depuis chaque côté.
À chaque étape, traitez le côté dont le maximum courant est le plus petit, car ce côté est le facteur limitant. Si max_left < max_right, l'eau au niveau du pointeur gauche est max_left - height[left] (le côté droit est suffisamment haut). Déplacez le pointeur gauche vers l'intérieur. Sinon, traitez symétriquement le pointeur droit. Aucun tableau précalculé n'est nécessaire.
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])) # 3Pourquoi l'approche à deux pointeurs fonctionne : l'invariant
L'idée clé est la suivante : lorsque nous traitons le pointeur gauche parce que height[left] < height[right], nous savons que max_right >= height[right] > height[left]. Par conséquent, la limite effective de l'eau à droite est au moins égale à height[right], qui est déjà supérieure à max_left. Ainsi, min(max_left, effective_max_right) = max_left, et la formule de l'eau se simplifie en max_left - height[left].
Nous n'avons pas besoin de connaître la valeur exacte de max_right : il suffit de savoir qu'elle est au moins égale à height[right] > height[left] pour utiliser max_left comme niveau d'eau. C'est cet invariant élégant qui rend possible l'utilisation d'un espace 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)Approche 3 : pile monotone (couches horizontales)
L'approche de la pile monotone calcule l'eau en couches horizontales entre des barres adjacentes. Maintenez une pile monotone décroissante d'indices. Lorsque la barre i est plus haute que le sommet j de la pile, une vallée se forme : la base est height[j], la paroi gauche est height[stack[-1]] après avoir retiré j, et la paroi droite est height[i]. L'eau remplit la vallée jusqu'à min(left_wall, right_wall) - floor, avec une largeur de i - stack[-1] - 1.
Chaque « vallée » est calculée lorsqu'une barre plus haute est rencontrée. Cela traite l'eau par segments rectangulaires délimités, ce qui est utile lorsque vous devez également suivre les barres qui contribuent au niveau de l'eau.
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])) # 9Parcours de la pile monotone
Examinons [0,1,0,2,1,0,1,3,...] avec l'approche par pile. Lorsque nous rencontrons la barre 3 (h=2) à i=3 : le sommet de la pile est i=2 (h=0), effectuez pop. La paroi gauche est i=1 (h=1), et la paroi droite est h=2. Hauteur d'eau = minimum(1,2)-0=1, largeur=3-1-1=1, aire=1. Poursuivez : le sommet de la pile i=1 (h=1) n'est pas inférieur à 2, arrêtez-vous. Empilez 3.
La méthode de la pile est plus complexe à implémenter que celle des deux pointeurs, mais elle révèle quelles barres précises forment chaque cellule d'eau. Cette compréhension est utile pour les questions complémentaires sur la reconstruction de la disposition de l'eau ou le comptage des vallées distinctes.
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)Comparaison des trois approches
Résumé des trois approches du piégeage de l'eau de pluie :
- Tableaux de préfixes : temps O(n), espace O(n). Les plus faciles à comprendre et à vérifier. Idéaux pour les entretiens où la clarté prime sur l'efficacité de l'espace.
- Deux pointeurs : temps O(n), espace O(1). Optimaux en temps comme en espace. Idéaux pour les questions complémentaires du type « pouvez-vous utiliser un espace O(1) ? ».
- Pile monotone : temps O(n), espace O(n). Traite l'eau par couches horizontales. Idéale lorsque vous devez savoir quelles barres contribuent à l'eau ou lorsque ce problème apparaît comme sous-problème dans un algorithme plus vaste fondé sur une pile.
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}')Conteneur avec le plus d'eau
Le problème Conteneur avec le plus d'eau (LeetCode 11) est souvent confondu avec le piégeage de l'eau de pluie. Ici, vous choisissez exactement deux barres et l'eau est délimitée uniquement par ces deux barres ; les barres intermédiaires ne comptent pas. Maximisez l'aire min(height[l], height[r]) × (r - l).
L'approche à deux pointeurs le résout de manière gloutonne : commencez aux deux extrémités (largeur maximale). Déplacez le pointeur correspondant à la barre la plus courte vers l'intérieur — déplacer celui de la barre la plus haute ne peut que réduire l'aire. Cette approche utilise un temps O(n) et un espace O(1), et elle est plus simple que l'approche à deux pointeurs du piégeage de l'eau de pluie, car aucun maximum courant n'est nécessaire.
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 mapAvancé : piégeage de l'eau de pluie II (3D)
Piégeage de l'eau de pluie II (LeetCode 407) étend le problème à une matrice de hauteurs en 2D. L'eau peut s'écouler dans les quatre directions et doit s'échapper par la bordure. La solution utilise un tas-min : initialisez le tas avec toutes les cellules de la bordure, puis effectuez une expansion de type BFS. Traitez la cellule dont la hauteur est la plus faible — tout voisin plus bas doit retenir de l'eau au moins jusqu'au niveau de la cellule actuelle.
Il s'agit d'un algorithme fondamentalement différent de celui du cas 1D, qui met à l'épreuve à la fois les opérations sur le tas et le parcours BFS. L'astuce des deux pointeurs en 1D ne se généralise pas à la 2D ; l'approche par tas, elle, se généralise.
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)) # 4Quand utiliser chaque méthode en entretien
Guide de décision pour l'entretien sur le piégeage de l'eau de pluie :
- Commencez par : les tableaux de préfixes — faciles à expliquer, intuitifs visuellement et manifestement corrects
- Question complémentaire « espace O(1) ? » : les deux pointeurs — expliquez que le côté le plus bas constitue le goulot d'étranglement
- Si l'intervieweur demande « une autre approche ? » : la pile monotone — expliquez le calcul par couches horizontales
Commencez toujours par définir clairement ce qui détermine le niveau de l'eau à chaque position (le minimum de la barre la plus haute de chaque côté) avant de passer au code. Cela montre que vous avez compris le problème et facilite l'explication de la solution.
# 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()Cas limites et erreurs courantes
Erreurs courantes dans le piégeage de l'eau de pluie :
- Oublier le minimum : le niveau de l'eau est
min(max_left, max_right), et non l'un des deux seuls maxima. Une barre a besoin de parois hautes des deux côtés. - Eau négative : utilisez
max(0, ...)pour borner les valeurs négatives à 0 lorsque la hauteur d'une position dépasse le niveau de l'eau. - Positions aux extrémités : les barres la plus à gauche et la plus à droite ne peuvent jamais retenir d'eau (il manque une paroi d'un côté). L'approche par tableau de préfixes gère cela naturellement, car
max_left[0] = height[0]rend toujours l'eau égale à 0 à l'indice 0. - Tableaux vides ou très courts : renvoyez 0 pour les tableaux comportant moins de 3 éléments.
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 waterVérification rapide
Vérifiez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que : le piégeage de l'eau de pluie se résout en trouvant le minimum des parois gauche et droite les plus hautes à chaque position, l'approche à deux pointeurs en espace O(1) fonctionne parce que le maximum courant du côté le plus bas est toujours la contrainte déterminante, et l'approche de la pile monotone calcule l'eau en couches horizontales, ce qui est utile lorsqu'elle est combinée à une autre logique fondée sur une pile. Ensuite, nous passons aux concepts de conception de systèmes, en commençant par le cadre RADIO pour des réponses d'entretien structurées.
Questions Fréquemment Posées
La leçon « Accumulation d’eau de pluie : pile et deux pointeurs » est-elle gratuite ?
Oui — le texte complet de « Accumulation d’eau de pluie : pile et deux pointeurs » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Accumulation d’eau de pluie : pile et deux pointeurs » ?
Résolvez trapping-rain-water avec l’approche par pile monotone, qui calcule des couches horizontales, et l’approche par deux pointeurs, qui calcule des colonnes verticales. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Accumulation d’eau de pluie : pile et deux pointeurs » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Pile monotone : croissante ou décroissante
- Plus grand rectangle dans un histogramme
- Maximum dans une fenêtre glissante avec une deque monotone
- Accumulation d’eau de pluie : pile et deux pointeurs