Trapping Rain Water
Una fila de barras se encuentra una al lado de la otra, cada una con una unidad de ancho: height[i] es la altura de la barra i. La lluvia cae sobre la fila y 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 número total de cuadrados unitarios de agua que contiene 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 permanece 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 agua sube hasta el nivel 3: contiene 2 unidades sobre la barra de 1, 3 sobre la de 0 y 1 sobre la de 2. El 1 cerca del final se encuentra entre el 5 y un 2, así que su nivel es 2 y contiene 1 unidad. 2 + 3 + 1 + 1 = 7.
- Entrada
- height = [4, 1, 3, 0, 5]
- Salida
- 8
- Explicación
- La pared más baja es el 4 de la izquierda, así que toda la depresión se llena hasta el nivel 4: 3 unidades sobre el 1, 1 sobre el 3 y 4 sobre el 0, lo que suma 8. El 5 de la derecha no eleva el nivel, porque el agua se desbordaría primero por el 4.
- 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 más allá, así que el agua se escurre y la respuesta es 0.
+17 pruebas ocultas al enviar
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 entonces 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. ¿A qué altura puede llegar 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 pasada desde cada extremo.Solo necesitas el menor de los dos máximos. Coloca un puntero en cada extremo y conserva 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 cantidad de agua y mueve ese puntero hacia dentro. Detente cuando los punteros se encuentren.
Solución
El agua sobre cada barra depende de barras que pueden estar muy lejos a ambos lados, así que observar solo las barras vecinas da un resultado incorrecto. La solución es una fórmula: el nivel sobre una barra es el menor de los valores máximos de las barras a su izquierda y a su derecha. Buscar esos dos máximos desde cada barra es lento; almacenarlos en dos arreglos hace que el algoritmo sea lineal, y dos punteros que siempre avanzan por el lado más bajo no necesitan arreglos.
Escanea ambos lados de cada barra
Correcto, pero no termina con las pruebas más grandes
Intuición
Cuenta el agua columna por columna. El agua sobre la barra i sube hasta que se derramaría por la más baja de sus dos paredes. La pared izquierda es la barra más alta en cualquier posición desde el índice 0 hasta i; la pared derecha es la barra más alta desde i hasta el final. Así que el nivel es min(leftMax, rightMax), y el agua sobre la barra i es ese nivel menos height[i].
Considera [0, 3, 1, 0, 2, 5, 1, 2] y la barra de altura 0 en el índice 3. La barra más alta a su izquierda mide 3 y, a su derecha, 5. El nivel es 3, así que allí se acumulan 3 unidades. Para la barra de altura 1 en el índice 6, las paredes miden 5 y 2: el nivel es 2 y retiene 1 unidad.
Ambos recorridos incluyen la barra i. Así se evita que el resultado sea negativo: cuando la barra i es más alta que todo lo que hay a un lado, el máximo de ese lado es su propia altura, el nivel equivale a su altura y retiene 0. Esta es también la razón por la que las barras de los extremos siempre retienen 0.
El problema es el costo. Para cada barra se recorre toda la fila, la mitad hacia la izquierda y la mitad hacia la derecha, así que el total es de n × n lecturas: 4 × 10^8 para 2 × 10^4 barras. Además, los recorridos repiten trabajo: la barra más alta a la izquierda del índice 5 es la barra más alta a la izquierda del índice 4, más una comparación; pero la fuerza bruta vuelve a calcularla desde cero.
Algoritmo
- Establece
wateren 0. - Para cada índice
i, busca desde 0 hastaipara encontrarleftMax. - Busca desde
ihasta el último índice para encontrarrightMax. - 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 waterPrecálcula la barra más alta de cada lado
Intuición
La fórmula no cambia; solo cambia la forma de obtener las dos paredes. 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 un array leftMax, construyendo cada elemento a partir del anterior. Una pasada de derecha a izquierda llena rightMax de la misma manera. Una tercera pasada suma min(leftMax[i], rightMax[i]) - height[i] para cada barra.
Para [0, 3, 1, 0, 2, 5, 1, 2]: leftMax = [0, 3, 3, 3, 3, 5, 5, 5] y rightMax = [5, 5, 5, 5, 5, 5, 2, 2]. Sus valores menores son los niveles [0, 3, 3, 3, 3, 5, 2, 2]. Resta las alturas y obtendrás [0, 0, 2, 3, 1, 0, 1, 0], que suma 7.
Cada pasada recorre cada barra una vez, así que el tiempo es O(n): unos 6 × 10^4 pasos para 2 × 10^4 barras, en lugar de 4 × 10^8. El costo son dos arrays adicionales de n números. Esta es la versión por la que conviene empezar en una entrevista: es difícil equivocarse, y el siguiente enfoque permite prescindir de los arrays; no es una idea diferente.
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 desplazan el lado inferior
Intuición
La fórmula solo necesita la menor de las dos paredes. Si puedes demostrar que la pared izquierda es la menor en algún índice, nunca necesitas para nada la pared derecha de ese índice. Dos punteros te dan esa prueba. Coloca left en el índice 0 y right en el último índice, y mantén leftMax y rightMax, las barras más altas por las que ha pasado cada puntero hasta ahora, incluida la barra sobre la que está.
El invariante: cada barra por la que los punteros ya han pasado no es más alta que la más alta de las dos barras sobre las que están ahora. Se cumple porque siempre mueves el puntero de la barra más baja, así que un puntero solo pasa por encima de una barra que no es más alta que la barra bajo el otro puntero.
Ahora supongamos que height[left] < height[right]. Por el invariante, leftMax es como máximo height[right], y height[right] es en sí misma una barra a la derecha de left. Así que la verdadera pared derecha de left tiene una altura al menos igual a leftMax, y el nivel en left es exactamente leftMax, independientemente de lo que haya entre los punteros. Suma leftMax - height[left] y mueve left un paso a la derecha. Cuando height[right] sea la barra más baja o de igual altura, haz lo mismo en el lado derecho. Actualiza el máximo acumulado antes de sumar el agua, para que la barra bajo el puntero cuente como su propia pared y el agua nunca sea negativa.
Recorre [0, 3, 1, 0, 2, 5, 1, 2]. Los punteros empiezan en 0 y 2: la izquierda es más baja, contiene 0. Después, 3 frente a 2: la derecha es más baja, rightMax pasa a ser 2, contiene 0. Luego, 3 frente a 1: la derecha vuelve a ser más baja, el 1 contiene 2-1 = 1. Luego, 3 frente a 5: ahora la izquierda es más baja, leftMax es 3, el 3 contiene 0, el 1 contiene 2, el 0 contiene 3 y el 2 contiene 1. Los punteros se encuentran en el 5. El total es 1 + 2 + 3 + 1 = 7, con una sola pasada y cuatro variables.
Algoritmo
- Establece
left = 0,right = n-1y asigna 0 aleftMax,rightMaxywater. - Mientras
left < right, comparaheight[left]conheight[right]. - Si la barra de la izquierda es más baja, aumenta
leftMaxhastaheight[left]si es necesario, sumaleftMax - height[left]y muevelefthacia la derecha. - De lo contrario, aumenta
rightMaxhastaheight[right]si es necesario, sumarightMax - height[right]y mueverighthacia la izquierda. - Devuelve
watercuando los punteros se encuentren; la barra en la que se encuentran es la más alta y no retiene agua.
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
La fórmula es breve, y la mayoría de las respuestas incorrectas se deben al orden de dos líneas o a qué lado mueves.
- Sumar el agua antes de actualizar el máximo acumulado. Si
height[left]es mayor queleftMax,leftMax - height[left]es negativo y el total disminuye. Primero actualiza el máximo y después suma. - Mover el puntero de la barra más alta. El nivel solo se conoce en el lado más bajo; mover el lado más alto utiliza una pared que no has demostrado que sea válida. Con
[4, 1, 3, 0, 5], esa versión devuelve 4 en lugar de 8. - Mirar solo los vecinos más cercanos. Las paredes de una barra pueden estar lejos: en
[3, 0, 2, 0, 1, 0, 4], la barra de 1 retiene agua hasta el nivel 3, determinado por barras que están a cuatro y dos pasos de distancia. La respuesta allí es 12. - Tratar los extremos del arreglo como paredes. El agua que pasa la primera o la última barra se desborda, así que una sola barra, dos barras o una fila que solo sube o solo baja retiene 0.
- Excluir la barra
ide sus propios recorridos en la solución de fuerza bruta. Entonces, una barra más alta que ambos lados obtiene una cantidad negativa. Inclúyela o limita el resultado a 0. - Desbordamiento en una variante que multiplica. Aquí la respuesta llega a aproximadamente 2 × 10^9 (dos barras de 10^5 alrededor de 19,998 celdas vacías), lo que todavía cabe en un entero con signo de 32 bits; en tus propias variantes, usa sumas de 64 bits.
Preguntas frecuentes4
¿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) espacio adicional: en cada paso, un puntero avanza hacia el interior, así que hay n-1 pasos. La versión con los arreglos leftMax y rightMax también se ejecuta en tiempo O(n), pero usa O(n) espacio. Recorrer ambos lados desde cada barra es O(n²), aproximadamente 4 × 10^8 lecturas para 2 × 10^4 barras.
¿Por qué la solución de dos punteros puede mover el lado más corto?
Cada barra ya recorrida no es más alta que la más alta de las dos barras actuales, porque solo se mueve el puntero inferior. Así que, cuando la barra izquierda es más baja, su máximo acumulado es como mucho la barra derecha, y la barra derecha es una pared real a su derecha. El nivel en el puntero izquierdo es su máximo acumulado, sin importar lo que haya entre los punteros, así que puedes dar por resuelta esa barra y seguir adelante.
¿Se puede resolver el problema de atrapar agua de lluvia con una pila?
Sí. Mantén una pila de índices cuyas alturas disminuyan de abajo hacia arriba. Cuando llega una barra más alta que la de la cima, saca la de la cima: es el suelo de un charco cuyas paredes son la nueva cima de la pila y la barra actual. Añade (min(two walls) - floor) × (distance between the walls - 1) y sigue sacando elementos mientras la barra actual sea más alta. La pila llena el agua en capas horizontales en lugar de columnas, en O(n) de tiempo y O(n) de espacio.
¿En qué se diferencia Trapping Rain Water de Container With Most Water?
En Container With Most Water eliges dos líneas y las líneas entre ellas no ocupan espacio, así que la respuesta es un rectángulo, el más grande. Aquí cada barra es sólida, el agua se acumula encima de cada barra y la respuesta es la suma de todas las barras. Ambos usan dos punteros que mueven el lado más bajo, por la misma razón: el lado más bajo es aquel cuyo resultado ya está determinado.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def trap(height):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
height = [0, 3, 1, 0, 2, 5, 1, 2]
Esperado
7