Trapping Rain Water: pila y dos punteros
Resuelva trapping-rain-water mediante el enfoque de pila monótona, que calcula capas horizontales, y el enfoque de dos punteros, que calcula columnas verticales.
Trapping Rain Water: pila y dos punteros es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Problema: atrapar agua de lluvia
Atrapar agua de lluvia (LeetCode 42) es uno de los problemas de entrevista más emblemáticos. Dado un arreglo de n enteros no negativos que representa un mapa de elevaciones en el que cada barra tiene un ancho de 1, calcule cuánta agua puede quedar atrapada entre las barras después de llover. El agua se acumula en cualquier valle situado entre barras más altas a ambos lados.
Para cada posición i, el nivel del agua es min(max_left[i], max_right[i]) - height[i]. Si el resultado es negativo, no queda agua atrapada (la barra es más alta que al menos uno de los límites). Existen tres enfoques: arreglos precalculados O(n)/O(n), dos punteros O(n)/O(1) y pila monótona 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)Enfoque 1: arreglos de máximos precalculados
La solución directa, con tiempo O(n) y espacio O(n), precalcula dos arreglos: max_left[i] = altura máxima desde el índice 0 hasta i, y max_right[i] = altura máxima desde el índice i hasta n-1. El agua en la posición i es max(0, min(max_left[i], max_right[i]) - height[i]).
Construir max_left requiere un único recorrido de izquierda a derecha; max_right requiere un recorrido de derecha a izquierda. Un recorrido final suma el agua. Este enfoque es claro y fácil de explicar, pero utiliza espacio adicional 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])) # 9Enfoque 2: dos punteros (espacio O(1))
El enfoque de dos punteros logra un tiempo O(n) y un espacio O(1). Utilice punteros izquierdo y derecho que comiencen en los dos extremos. Mantenga max_left y max_right como los máximos acumulados vistos hasta el momento desde cada lado.
En cada paso, procese el lado cuyo máximo acumulado sea menor, porque ese lado es el factor limitante. Si max_left < max_right, el agua en el puntero izquierdo es max_left - height[left] (el lado derecho tiene suficiente altura). Mueva el puntero izquierdo hacia dentro. De lo contrario, procese simétricamente el puntero derecho. No se necesitan arreglos precalculados.
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])) # 3Por qué funciona el enfoque de dos punteros: la invariante
La idea clave es la siguiente: cuando procesamos el puntero izquierdo porque height[left] < height[right], sabemos que max_right >= height[right] > height[left]. Por lo tanto, el límite efectivo del agua a la derecha es como mínimo height[right], que ya es mayor que max_left. Así que min(max_left, effective_max_right) = max_left, y la fórmula del agua se simplifica a max_left - height[left].
No necesitamos conocer el valor exacto de max_right; basta con saber que es al menos height[right] > height[left] para utilizar max_left como nivel del agua. Esta es la elegante invariante que hace posible utilizar espacio 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)Enfoque 3: Pila monótona (capas horizontales)
El enfoque de la pila monótona calcula el agua en capas horizontales entre barras adyacentes. Mantenga una pila monótona decreciente de índices. Cuando la barra i es más alta que el tope j de la pila, se forma un valle: el suelo es height[j], la pared izquierda es height[stack[-1]] después de extraer j y la pared derecha es height[i]. El agua llena el valle hasta min(left_wall, right_wall) - floor, con un ancho de i - stack[-1] - 1.
Cada «valle» se calcula cuando se encuentra una barra más alta. De este modo, el agua se procesa en segmentos rectangulares delimitados, lo que resulta útil cuando también necesita realizar un seguimiento de qué barras contribuyen al nivel del agua.
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])) # 9Recorrido de la pila monótona
Recorramos [0,1,0,2,1,0,1,3,...] con el enfoque de pila. Cuando encontramos la barra 3 (h=2) en i=3: el tope de la pila es i=2 (h=0), así que la extraemos. La pared izquierda es i=1 (h=1) y la pared derecha es h=2. La altura del agua = min(1,2)-0=1, el ancho=3-1-1=1 y el área=1. Continuamos: el tope de la pila i=1 (h=1) no es menor que 2, por lo que detenemos el proceso. Insertamos 3 en la pila.
El método de la pila es más complejo de implementar que el de dos punteros, pero muestra qué barras concretas forman cada celda de agua. Este conocimiento resulta útil en preguntas posteriores sobre cómo reconstruir la distribución del agua o contar valles distintos.
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)Comparación de los tres enfoques
Resumen de los tres enfoques para atrapar agua de lluvia:
- Arrays de prefijos: tiempo O(n), espacio O(n). Son los más fáciles de entender y verificar. Son la mejor opción en entrevistas en las que la claridad es más importante que la eficiencia espacial.
- Dos punteros: tiempo O(n), espacio O(1). Son óptimos tanto en tiempo como en espacio. Son la mejor opción para preguntas posteriores como «¿puede hacerlo con espacio O(1)?».
- Pila monótona: tiempo O(n), espacio O(n). Procesa el agua en capas horizontales. Es la mejor opción cuando necesita saber qué barras contribuyen o cuando este problema aparece como subproblema en un algoritmo mayor basado en pilas.
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}')Contenedor con más agua
Contenedor con más agua (LeetCode 11) suele confundirse con atrapar agua de lluvia. Aquí se eligen exactamente dos barras y el agua queda limitada únicamente por ellas (las barras internas no importan). Maximice el área min(height[l], height[r]) × (r - l).
Los dos punteros lo resuelven de forma voraz: comience en ambos extremos (ancho máximo). Mueva hacia dentro el puntero que apunta a la barra más corta; mover el que apunta a la barra más alta solo puede reducir el área. Este enfoque requiere tiempo O(n) y espacio O(1), y es más sencillo que el de dos punteros para atrapar agua de lluvia porque no necesita mantener ningún máximo acumulado.
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 mapAvanzado: Atrapar agua de lluvia II (3D)
Atrapar agua de lluvia II (LeetCode 407) amplía el problema a una matriz de alturas bidimensional. El agua puede fluir en las cuatro direcciones y debe escapar por el borde. La solución utiliza un montículo mínimo: inicialice el montículo con todas las celdas del borde y, después, realice una expansión similar a BFS. Procese la celda con menor altura; cualquier vecina más baja debe contener agua al menos hasta el nivel de la celda actual.
Se trata de un algoritmo fundamentalmente distinto del caso unidimensional y pone a prueba tanto las operaciones con montículos como el recorrido BFS. El truco de los dos punteros del caso 1D no se generaliza a 2D; el enfoque basado en montículos 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)) # 4Cuándo usar cada método en entrevistas
Guía para decidir el enfoque en una entrevista sobre cómo atrapar agua de lluvia:
- Comience con: arrays de prefijos — son fáciles de explicar, visualmente intuitivos y claramente correctos
- Pregunta posterior «¿espacio O(1)?»: dos punteros — explique que el máximo acumulado del lado más bajo es el cuello de botella
- Si el entrevistador pregunta «¿otro enfoque?»: pila monótona — explique el cálculo por capas horizontales
Comience siempre por definir con claridad qué determina el nivel del agua en cada posición (el mínimo de la barra más alta de cada lado) antes de pasar al código. Esto demuestra que comprende el problema y facilita la explicación de la solución.
# 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()Casos límite y errores comunes
Errores comunes al resolver el problema de atrapar agua de lluvia:
- Olvidar min: el nivel del agua es
min(max_left, max_right), no solo uno de esos valores. Una barra necesita paredes altas a ambos lados. - Agua negativa: utilice
max(0, ...)para limitar a 0 los valores negativos cuando la altura de una posición supera el nivel del agua. - Posiciones de los extremos: las barras situadas más a la izquierda y más a la derecha nunca pueden contener agua (no tienen una pared en uno de los lados). El enfoque de arrays de prefijos gestiona esto de forma natural, ya que
max_left[0] = height[0]hace que el agua siempre sea 0 en el índice 0. - Arrays vacíos o muy pequeños: devuelva 0 para arrays con menos de 3 elementos.
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 waterComprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que: atrapar agua de lluvia se resuelve encontrando el mínimo entre las paredes izquierdas y derechas más altas en cada posición, el enfoque de dos punteros con espacio O(1) funciona porque el máximo acumulado del lado más bajo siempre es la restricción determinante y el enfoque de la pila monótona calcula el agua en capas horizontales, lo que resulta útil al combinarlo con otra lógica basada en pilas. A continuación pasaremos a conceptos de diseño de sistemas, empezando por el marco RADIO para estructurar las respuestas en entrevistas.
Preguntas frecuentes
¿La lección «Trapping Rain Water: pila y dos punteros» es gratis?
Sí — el texto completo de «Trapping Rain Water: pila y dos punteros» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Trapping Rain Water: pila y dos punteros»?
Resuelva trapping-rain-water mediante el enfoque de pila monótona, que calcula capas horizontales, y el enfoque de dos punteros, que calcula columnas verticales. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Trapping Rain Water: pila y dos punteros»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Pila monótona: creciente frente a decreciente
- Rectángulo más grande en un histograma
- Máximo de ventana deslizante con deque monótona
- Trapping Rain Water: pila y dos punteros