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
Entrada:
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Salida esperada:
expected = 6Entrada:
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.
Entrada:
heights = [3, 2, 1]
Salida esperada:
expected = 0Entrada:
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.