Todos los desafíos
Difícil 2 resueltos 33.3% de aceptación

Trapping Rain Water

Compute how much rain water an elevation map holds.

Lo que aprenderás

  • Calcular el agua sobre cada barra
  • Usar los máximos de izquierda y derecha
  • Resolverlo con dos punteros en O(n)

Problema

Bars of width 1 have the given heights. After rain, water collects above each bar up to the lower of the tallest bars on its left and right. Compute the total trapped water. An O(n) two-pointer solution is expected.

Implement trapped_water(heights).

Input

heights: Bar heights from left to right.

Output

Return the total units of water.

Restricciones

0 ≤ length ≤ 200,000; 0 ≤ height ≤ 100,000

Ejemplos

Ejemplo 1
Entrada:
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Salida esperada:
expected = 6
Entrada:
std::vector<long long> heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

Salida esperada:
long long expected = 6;
Entrada:
long[] heights = new long[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

Salida esperada:
long expected = 6;

Explicación

Water fills the dips: 1 + 1 + 2 + 1 + 1 = 6 units.

Ejemplo 2
Entrada:
heights = [3, 2, 1]

Salida esperada:
expected = 0
Entrada:
std::vector<long long> heights = {3, 2, 1};

Salida esperada:
long long expected = 0;
Entrada:
long[] heights = new long[] {3, 2, 1};

Salida esperada:
long expected = 0;

Explicación

Heights only go down, so water runs off: 0.

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

El nivel de agua en cada posición está limitado por la barra más alta más corta vista a la izquierda y a la derecha.

Pista 2

Lleva un registro de los límites desde ambos extremos, avanzando siempre el lado con el límite actual menor.

Pista 3

Ten cuidado con la entrada vacía y con las mesetas de altura igual; ahí solo el lado menor puede determinar el agua atrapada.

Complejidad esperada

tiempo O(n), espacio extra O(1)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 885 ms - 5/5 Ver código
2 KKosake82 Python 933 ms - 4/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 2 soluciones completas abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.