Trapping Rain Water
Una fila de barras está dispuesta una al lado de otra, cada una de una unidad de ancho: height[i] es la altura de la barra i. La lluvia se acumula en los huecos entre las barras. El agua permanece sobre una barra solo si hay una barra más alta en algún lugar a su izquierda y otra en algún lugar a su derecha; más allá de la primera y la última barra, se escurre. Devuelve el total de unidades de agua que retiene la fila.
Función
- heightinteger-array
- la altura de cada barra, de izquierda a derecha
- Devuelveinteger
- las unidades totales de agua atrapada
Restricciones
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- Cada barra tiene una unidad de ancho, y el agua no se queda más allá de la primera ni de la última barra.
Ejemplos
- Entrada
- height = [0, 3, 1, 0, 2, 5, 1, 2]
- Salida
- 7
- Explicación
- Entre el 3 y el 5, el nivel es 3: 2 unidades por encima del 1, 3 por encima del 0, 1 por encima del 2. El 1 posterior se encuentra entre el 5 y un 2, así que vale 1. Eso da 7.
- Entrada
- height = [4, 1, 3, 0, 5]
- Salida
- 8
- Explicación
- La pared más baja es la de 4, así que el hueco se llena hasta el nivel 4: 3 unidades sobre el 1, 1 sobre el 3, 4 sobre el 0, lo que suma 8. El agua se derrama por encima del 4 antes de que el 5 importe.
- Entrada
- height = [1, 2, 4, 2, 1]
- Salida
- 0
- Explicación
- Las barras suben hasta 4 y vuelven a bajar. Cada barra tiene un lado sin nada más alto detrás, así que el agua se escurre y la respuesta es 0.
Para ir más allá
Supón que las barras forman una cuadrícula 2D de alturas y el agua puede escapar en las cuatro direcciones. ¿Cómo contarías después el agua atrapada?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Olvídate de toda la fila y fíjate en una sola barra. ¿Qué altura puede alcanzar el agua por encima de la barra
i, y qué barras determinan esa altura?El nivel del agua por encima de la barra
ies el menor de dos números: la barra más alta desde el inicio hastaiy la barra más alta desdeihasta el final. La barraicontiene ese nivel menos su propia altura. Ambos máximos acumulados se pueden calcular en una sola pasada desde cada extremo.Solo necesitas el menor de los dos máximos. Coloca un puntero en cada extremo y mantén la barra más alta que haya pasado cada puntero. El nivel del puntero que esté sobre la barra más baja queda determinado por su propio máximo acumulado: añade esa agua y mueve ese puntero hacia el interior. Detente cuando los punteros se encuentren.
Solución
El agua sobre una barra depende de las barras que pueden estar muy lejos a ambos lados. Su nivel es el menor entre la barra más alta a su izquierda y la barra más alta a su derecha, y la barra retiene ese nivel menos su propia altura. Los enfoques solo difieren en cómo encuentran esos dos máximos.
Escanea ambos lados desde cada compás
Correcto, pero no termina con las pruebas más grandes
Intuición
Para cada barra i, recorre desde 0 hasta i para encontrar la barra más alta a la izquierda y desde i hasta el final para encontrar la más alta a la derecha; después suma min(leftMax, rightMax) - height[i]. Incluir la barra i en ambos recorridos evita que la cantidad sea negativa y asigna 0 a las barras de los extremos.
Cada barra recorre toda la fila: n = 2 × 10^4 significa 4 × 10^8 lecturas, la mayoría repite el recorrido de la barra anterior.
Algoritmo
- Establece
wateren 0. - Para cada índice
i, buscaleftMaxdesde 0 hastai. - Busca
rightMaxdesdeihasta el último índice. - Suma
min(leftMax, rightMax) - height[i]awater. - Devuelve
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 waterPrecalcula la barra más alta de cada lado
Intuición
La barra más alta desde 0 hasta i es la mayor entre la barra más alta desde 0 hasta i-1 y height[i]. Así que una pasada de izquierda a derecha llena leftMax, construyendo cada entrada a partir de la anterior, y una pasada de derecha a izquierda llena rightMax. Una tercera pasada aplica la fórmula.
Para [0, 3, 1, 0, 2, 5, 1, 2], los niveles min(leftMax[i], rightMax[i]) son [0, 3, 3, 3, 3, 5, 2, 2]. Al restar las alturas, se obtiene [0, 0, 2, 3, 1, 0, 1, 0], cuya suma es 7. El tiempo es O(n), a costa de dos arreglos de n números.
Algoritmo
- Rellena
leftMaxde izquierda a derecha:leftMax[0] = height[0], despuésleftMax[i] = max(leftMax[i-1], height[i]). - Rellena
rightMaxde derecha a izquierda:rightMax[n-1] = height[n-1], despuésrightMax[i] = max(rightMax[i+1], height[i]). - Para cada índice, suma
min(leftMax[i], rightMax[i]) - height[i]al total. - Devuelve el total.
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 waterDos punteros que mueven el lado inferior
Intuición
La fórmula solo necesita la pared más baja, y dos punteros pueden demostrar cuál es. Inicia left en 0 y right en el último índice, lleva un registro de leftMax y rightMax, la barra más alta que ha pasado cada puntero, incluida la que está bajo él, y mueve siempre el puntero que está en la barra más baja. Entonces todas las barras que ya se han pasado tienen una altura menor o igual que la barra más alta de las dos barras actuales, porque un puntero solo pasa una barra que no es más alta que la que está bajo el otro puntero.
Supongamos que height[left] < height[right]. Por el invariante, leftMax es menor o igual que height[right], una barra situada a la derecha de left. Así que la pared derecha de left tiene una altura de al menos leftMax, y su nivel es exactamente leftMax, sin importar lo que haya entre los punteros. Cuando la barra derecha es más baja o igual, el argumento simétrico resuelve right.
Algoritmo
- Establece
left = 0,right = n-1, yleftMax,rightMaxywateren 0. - Mientras
left < right: siheight[left] < height[right], aumentaleftMaxaheight[left]si es necesario, sumaleftMax - height[left]y muevelefta la derecha. - De lo contrario, haz lo mismo en el lado derecho y mueve
righta la izquierda. - Devuelve
water. La barra donde se encuentran los punteros es la más alta y no contiene nada.
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
Errores comunes y casos límite
- Sumar el agua antes de actualizar el máximo acumulado. Cuando
height[left]superaleftMax, la cantidad es negativa y el total disminuye. - Mover el puntero de la barra más alta, cuyo nivel no está demostrado. En
[4, 1, 3, 0, 5], esa versión devuelve 4 en lugar de 8. - Fijarse solo en las barras vecinas más cercanas. En
[3, 0, 2, 0, 1, 0, 4], la barra de altura 1 se llena hasta el nivel 3, determinado por barras que están a cuatro y dos posiciones de distancia; la respuesta es 12. - Tratar los extremos del arreglo como paredes. El agua se escurre por ellos, así que una barra, dos barras o una fila que solo sube o solo baja retiene 0.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Trapping Rain Water?
La solución de dos punteros se ejecuta en tiempo O(n) y usa O(1) de espacio adicional, ya que en cada paso mueve un puntero hacia el interior. La versión con los arreglos leftMax y rightMax también se ejecuta en tiempo O(n), pero usa O(n) de espacio. Recorrer ambos lados desde cada barra es O(n²).
¿Se puede resolver el problema de atrapar agua de lluvia con una pila?
Sí. Mantén una pila de índices con alturas decrecientes. Cuando aparece una barra más alta, saca el elemento superior: es el suelo de una piscina delimitada por la nueva cima y la barra actual. Suma (min(two walls) - floor) × (distance between the walls - 1) y sigue sacando elementos. Así se calcula el agua en capas horizontales, en tiempo y espacio O(n).
¿En qué se diferencia Trapping Rain Water de Container With Most Water?
En «Container With Most Water», las líneas no ocupan espacio y la respuesta es el rectángulo más grande entre dos líneas. Aquí cada barra es sólida y la respuesta suma el agua de todas las barras. En ambos casos se mueve el lado más bajo por la misma razón: su resultado ya está decidido.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def trap(height):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
height = [0, 3, 1, 0, 2, 5, 1, 2]
Salida Esperada
7