Lluvia entre las rocas
- O(n²) · Muy difícil
- Plan completo
- Python
- JavaScript
- listas
- ciclos
- comparaciones
Enunciado
La tormenta ya pasó, y en la orilla quedaron charcos entre las rocas.
Las rocas están en fila, cada una mide uno de ancho, y la lista trae sus alturas (enteros de 0 en adelante; puede venir vacía).
Sobre cada roca el agua sube hasta la más baja de dos alturas: la de la roca más alta a su izquierda y la de la más alta a su derecha. Lo que pase de la roca es agua; si esa altura no pasa de la roca, ahí no hay.
La primera y la última roca nunca guardan: les falta un lado.
Con [3, 0, 2, 0, 4], la más alta a la izquierda de las de en medio es 3 y a la derecha es 4, así que el agua llega a 3. Sobre el primer 0 caben 3, sobre el 2 cabe 1 y sobre el otro 0 caben 3: regresas 7.
Regresa el total de agua como entero. Sin rocas, o con una o dos, es 0.
Ejemplos
El ejemplo
[3, 0, 2, 0, 4] → 7
Una orilla larga
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] → 6
Las rocas solo suben
[1, 2, 3, 4] → 0
La derecha es la más baja
[4, 0, 1] → 1
Una sola roca
[5] → 0
Además de estas, el reto tiene pruebas ocultas que se revelan al enviar tu solución.
Empiezas con esto
Python
def agua_atrapada(rocas):
passJavaScript
function aguaAtrapada(rocas) {
}Se abre en el navegador, con el editor y las pruebas. Este reto es del plan completo; los de O(1) y O(log n) son gratis.
Más retos de O(n²)
- Los avisperos del viverorejillas · textos · ciclos
- Los caballos del kancomparaciones · ciclos · listas
- Los caminos por la obrarecursión · rejillas · diccionarios
- Los camiones que pasaronlistas · comparaciones · condicionales
- Los charcos del patiorejillas · recursión · ciclos
- Los códices gemelosciclos · textos · índices