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.
Restrições
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 100,000
Exemplos
Entrada:
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Saída esperada:
expected = 6Entrada:
std::vector<long long> heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Saída esperada:
long long expected = 6;Entrada:
long[] heights = new long[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Saída esperada:
long expected = 6;Explicação
Water fills the dips: 1 + 1 + 2 + 1 + 1 = 6 units.
Entrada:
heights = [3, 2, 1]
Saída esperada:
expected = 0Entrada:
std::vector<long long> heights = {3, 2, 1};
Saída esperada:
long long expected = 0;Entrada:
long[] heights = new long[] {3, 2, 1};
Saída esperada:
long expected = 0;Explicação
Heights only go down, so water runs off: 0.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
A água em cada posição é limitada pela menor das maiores barras vistas à esquerda e à direita.
Dica 2
Acompanhe os limites dos dois lados, avançando sempre o lado com o menor limite atual.
Dica 3
Cuidado com entrada vazia e platôs de mesma altura; ali, só o lado menor pode determinar a água presa.
Complexidade esperada
tempo O(n), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.