Acúmulo de água da chuva: pilha e dois ponteiros
Resolva o problema do acúmulo de água da chuva usando tanto a abordagem de pilha monotônica, que calcula camadas horizontais, quanto a abordagem de dois ponteiros, que calcula colunas verticais.
Acúmulo de água da chuva: pilha e dois ponteiros é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Problema: retenção de água da chuva
Retenção de água da chuva (LeetCode 42) é um dos problemas mais conhecidos em entrevistas. Dado um vetor de n inteiros não negativos que representa um mapa de elevação, em que cada barra tem largura 1, calcule quanta água pode ficar retida entre as barras depois da chuva. A água preenche qualquer vale entre barras mais altas dos dois lados.
Para cada posição i, o nível da água é min(max_left[i], max_right[i]) - height[i]. Se esse valor for negativo, nenhuma água ficará retida (a barra é mais alta que pelo menos um dos limites). Existem três abordagens: vetores pré-calculados O(n)/O(n), dois ponteiros O(n)/O(1) e pilha monotônica O(n)/O(n).
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
# Water trapped at each position:
# pos 2: min(1,3)-0=1
# pos 4: min(2,3)-1=1
# pos 5: min(2,3)-0=2
# pos 6: min(2,3)-1=1
# pos 9: min(3,2)-1=1
# Total = 6
print('height:', height)
print('Expected trapped water: 6')
# Visualise
max_h = max(height)
for row in range(max_h, 0, -1):
line = ''
for h in height:
line += '#' if h >= row else ' '
print(line)Abordagem 1: vetores de máximos pré-calculados
A solução direta, com tempo O(n) e espaço O(n), calcula previamente dois vetores: max_left[i] = altura máxima do índice 0 até i e max_right[i] = altura máxima do índice i até n-1. A água na posição i é max(0, min(max_left[i], max_right[i]) - height[i]).
Construir max_left exige uma única passagem da esquerda para a direita; max_right exige uma passagem da direita para a esquerda. Uma passagem final soma a água. Essa abordagem é clara e fácil de explicar, mas usa espaço adicional O(n).
def trap_prefix(height):
n = len(height)
if n < 3:
return 0
max_left = [0] * n
max_right = [0] * n
max_left[0] = height[0]
for i in range(1, n):
max_left[i] = max(max_left[i-1], height[i])
max_right[-1] = height[-1]
for i in range(n-2, -1, -1):
max_right[i] = max(max_right[i+1], height[i])
water = 0
for i in range(n):
water += max(0, min(max_left[i], max_right[i]) - height[i])
return water
print(trap_prefix([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_prefix([4,2,0,3,2,5])) # 9Abordagem 2: dois ponteiros (espaço O(1))
A abordagem de dois ponteiros alcança tempo O(n) e espaço O(1). Use ponteiros esquerdo e direito começando nas duas extremidades. Mantenha max_left e max_right como os máximos acumulados observados até o momento a partir de cada lado.
A cada passo, processe o lado cujo máximo acumulado é menor — porque esse lado é o fator limitante. Se max_left < max_right, a água no ponteiro esquerdo é max_left - height[left] (o lado direito é alto o suficiente). Mova o ponteiro esquerdo para dentro. Caso contrário, processe o ponteiro direito simetricamente. Não são necessários vetores pré-calculados.
def trap_two_pointer(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left] # new max on the left
else:
water += max_left - height[left] # trapped by max_left
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap_two_pointer([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_two_pointer([4,2,0,3,2,5])) # 9
print(trap_two_pointer([3,0,3])) # 3Por que dois ponteiros funcionam: o invariante
A ideia principal é: quando processamos o ponteiro esquerdo porque height[left] < height[right], sabemos que max_right >= height[right] > height[left]. Portanto, o limite efetivo da água à direita é pelo menos height[right], que já é maior que max_left. Assim, min(max_left, effective_max_right) = max_left, e a fórmula da água se simplifica para max_left - height[left].
Não precisamos conhecer o valor exato de max_right — basta saber que ele é pelo menos height[right] > height[left] para usar max_left como nível da água. Esse é o invariante elegante que torna possível usar espaço O(1).
# Trace two-pointer on [4, 2, 0, 3, 2, 5]
height = [4, 2, 0, 3, 2, 5]
left, right = 0, len(height) - 1
max_l = max_r = water = 0
print('height:', height)
print(f'{'Step':5} {'L':3} {'R':3} {'maxL':5} {'maxR':5} {'water':6} {'total':6}')
step = 0
while left < right:
side = 'L' if height[left] < height[right] else 'R'
if side == 'L':
if height[left] >= max_l: max_l = height[left]
else:
w = max_l - height[left]; water += w
left += 1
else:
if height[right] >= max_r: max_r = height[right]
else:
w = max_r - height[right]; water += w
right -= 1
step += 1
print(f'{step:5} {left:3} {right:3} {max_l:5} {max_r:5} {water:6}')
print('Total trapped:', water)Abordagem 3: Pilha Monotônica (Camadas Horizontais)
A abordagem da pilha monotônica calcula a água em camadas horizontais entre barras adjacentes. Mantenha uma pilha monotônica decrescente de índices. Quando a barra i é mais alta que o topo j da pilha, forma-se um vale: a base é height[j], a parede esquerda é height[stack[-1]] depois de remover j, e a parede direita é height[i]. A água preenche o vale até min(left_wall, right_wall) - floor, com largura i - stack[-1] - 1.
Cada 'vale' é calculado quando uma barra mais alta é encontrada. Isso processa a água em segmentos retangulares delimitados, o que é útil quando também é necessário acompanhar quais barras contribuem para o nível da água.
def trap_stack(height):
stack = [] # monotonic decreasing indices
water = 0
for i in range(len(height)):
while stack and height[stack[-1]] < height[i]:
bottom_idx = stack.pop() # the floor of the valley
if not stack:
break # no left wall, no water
left_idx = stack[-1]
floor = height[bottom_idx]
water_height = min(height[left_idx], height[i]) - floor
width = i - left_idx - 1
water += water_height * width
stack.append(i)
return water
print(trap_stack([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_stack([4,2,0,3,2,5])) # 9Rastreando a Pilha Monotônica
Vamos rastrear [0,1,0,2,1,0,1,3,...] usando a abordagem da pilha. Quando encontramos a barra 3 (h=2) em i=3: o topo da pilha é i=2 (h=0); removemo-lo. A parede esquerda é i=1 (h=1), e a parede direita é h=2. Altura da água = min(1,2)-0=1, largura=3-1-1=1, área=1. Continuando: o topo da pilha i=1 (h=1) não é menor que 2; paramos. Empilhamos 3.
O método da pilha é mais complexo de implementar do que o de dois ponteiros, mas revela quais barras específicas formam cada célula de água. Essa informação é útil em perguntas de acompanhamento sobre a reconstrução da disposição da água ou a contagem de vales distintos.
def trap_stack_trace(height):
stack = []
water = 0
for i in range(len(height)):
print(f'i={i} h={height[i]}: stack={[height[s] for s in stack]}')
while stack and height[stack[-1]] < height[i]:
bot = stack.pop()
if not stack:
print(f' Pop {height[bot]}: no left wall, skip')
break
left = stack[-1]
h = min(height[left], height[i]) - height[bot]
w = i - left - 1
water += h * w
print(f' Pop {height[bot]}: floor={height[bot]}, left_wall={height[left]}, right_wall={height[i]}, h={h}, w={w}, +{h*w}')
stack.append(i)
return water
result = trap_stack_trace([0,1,0,2,1,0,1,3,2,1,2,1])
print('Total:', result)Comparação das Três Abordagens
Resumo das três abordagens para prender água da chuva:
- Vetores de prefixos: tempo O(n), espaço O(n). Mais fácil de entender e verificar. Melhor para entrevistas nas quais a clareza é mais valorizada do que a eficiência de espaço.
- Dois ponteiros: tempo O(n), espaço O(1). Ideal tanto em tempo quanto em espaço. Melhor para perguntas de acompanhamento como 'é possível usar espaço O(1)?'.
- Pilha monotônica: tempo O(n), espaço O(n). Processa a água em camadas horizontais. Melhor quando é necessário saber quais barras contribuem ou quando esse problema aparece como um subproblema em um algoritmo maior baseado em pilha.
height = [0,1,0,2,1,0,1,3,2,1,2,1]
# All three methods — verify they agree
def trap_prefix(h):
n = len(h)
ml = [0]*n; mr = [0]*n; ml[0]=h[0]; mr[-1]=h[-1]
for i in range(1,n): ml[i]=max(ml[i-1],h[i])
for i in range(n-2,-1,-1): mr[i]=max(mr[i+1],h[i])
return sum(max(0,min(ml[i],mr[i])-h[i]) for i in range(n))
def trap_two_ptr(h):
l,r,ml,mr,w = 0,len(h)-1,0,0,0
while l<r:
if h[l]<h[r]:
ml=max(ml,h[l]); w+=ml-h[l]; l+=1
else:
mr=max(mr,h[r]); w+=mr-h[r]; r-=1
return w
def trap_stk(h):
stk,w = [],[]
for i in range(len(h)):
while stk and h[stk[-1]]<h[i]:
b=stk.pop()
if not stk: break
w.append(max(0,min(h[stk[-1]],h[i])-h[b])*(i-stk[-1]-1))
stk.append(i)
return sum(w)
for h in [height, [4,2,0,3,2,5], [3,0,3], [1,0,1]]:
p=trap_prefix(h); t=trap_two_ptr(h); s=trap_stk(h)
print(f'{h}: prefix={p}, two-ptr={t}, stack={s}, match={p==t==s}')Recipiente com Mais Água
Recipiente com Mais Água (LeetCode 11) costuma ser confundido com o problema de prender água da chuva. Aqui, você escolhe exatamente duas barras, e a água é delimitada somente por essas duas barras (as barras internas não importam). Maximize a área min(height[l], height[r]) × (r - l).
Dois ponteiros resolvem o problema de forma gulosa: comece pelas duas extremidades (largura máxima). Mova o ponteiro menor para dentro — mover o maior só pode diminuir a área. Isso usa tempo O(n) e espaço O(1), sendo mais simples do que a abordagem de dois ponteiros para prender água da chuva, pois não é necessário manter um máximo acumulado.
def max_water_container(height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)
# Move the shorter bar: moving taller bar can only reduce min
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
print(max_water_container([1,8,6,2,5,4,8,3,7])) # 49: bars 8 and 7
print(max_water_container([1,1])) # 1
print(max_water_container([4,3,2,1,4])) # 16
# Key difference from trapping rain water:
# Container: choose 2 bars, water fills freely between them (no internal barriers)
# Trapping: water fills ALL valleys in the full elevation mapAvançado: Prender Água da Chuva II (3D)
Prender Água da Chuva II (LeetCode 407) estende o problema para uma matriz de alturas 2D. A água pode fluir nas quatro direções e precisa escapar pela borda. A solução usa uma fila de prioridade mínima: inicialize a fila com todas as células da borda e, em seguida, faça uma expansão semelhante a BFS. Processe a célula com a menor altura — qualquer vizinho mais baixo deverá reter água pelo menos até o nível da célula atual.
Este é um algoritmo fundamentalmente diferente do caso 1D e avalia tanto as operações da fila de prioridade quanto o percurso BFS. O truque de dois ponteiros do caso 1D não se generaliza para 2D; a abordagem da fila de prioridade, sim.
import heapq
def trap_rain_water_2d(heightMap):
if not heightMap or not heightMap[0]:
return 0
m, n = len(heightMap), len(heightMap[0])
visited = [[False]*n for _ in range(m)]
heap = [] # (height, row, col)
# Add all border cells to the heap
for i in range(m):
for j in [0, n-1]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
for j in range(n):
for i in [0, m-1]:
if not visited[i][j]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
total = 0
max_h = 0
while heap:
h, r, c = heapq.heappop(heap)
max_h = max(max_h, h)
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0<=nr<m and 0<=nc<n and not visited[nr][nc]:
visited[nr][nc] = True
total += max(0, max_h - heightMap[nr][nc])
heapq.heappush(heap, (max(max_h, heightMap[nr][nc]), nr, nc))
return total
map2d = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
print(trap_rain_water_2d(map2d)) # 4Quando Usar Cada Método em Entrevistas
Guia de decisão para a entrevista sobre como prender água da chuva:
- Comece com: vetores de prefixos — fáceis de explicar, visualmente intuitivos e claramente corretos
- Pergunta de acompanhamento 'espaço O(1)?': dois ponteiros — explique o invariante de que o lado menor é o gargalo
- Se o entrevistador perguntar 'outra abordagem?': pilha monotônica — explique o cálculo em camadas horizontais
Sempre comece definindo claramente o que determina o nível da água em cada posição (o mínimo da barra mais alta de cada lado) antes de partir para o código. Isso demonstra compreensão do problema e torna a solução mais fácil de explicar.
# Quick summary of all three approaches
approaches = [
{
'name': 'Prefix max arrays',
'time': 'O(n)', 'space': 'O(n)',
'description': '3 passes: build max_left, max_right, sum water column-by-column',
},
{
'name': 'Two pointers',
'time': 'O(n)', 'space': 'O(1)',
'description': 'Process smaller side: its max is the limiting wall, no array needed',
},
{
'name': 'Monotonic stack',
'time': 'O(n)', 'space': 'O(n)',
'description': 'Compute water in horizontal layers when a taller bar is encountered',
},
]
for a in approaches:
print(f'{a["name"]} [{a["time"]} / {a["space"]}]')
print(f' {a["description"]}')
print()Casos Limite e Erros Comuns
Erros comuns ao resolver o problema de prender água da chuva:
- Esquecer o mínimo: o nível da água é
min(max_left, max_right), não apenas um dos dois valores. Uma barra precisa de paredes altas em ambos os lados. - Água negativa: use
max(0, ...)para limitar valores negativos a 0 quando a altura de uma posição exceder o nível da água. - Posições nas extremidades: as barras mais à esquerda e mais à direita nunca podem reter água (não há parede em um dos lados). A abordagem de vetores de prefixos trata isso naturalmente, pois
max_left[0] = height[0]faz com que a água seja sempre 0 no índice 0. - Vetores vazios ou muito pequenos: retorne 0 para vetores com menos de 3 elementos.
def trap(height):
n = len(height)
if n < 3:
return 0 # need at least 3 bars to trap anything
left, right = 0, n - 1
max_l = max_r = water = 0
while left < right:
if height[left] <= height[right]:
if height[left] >= max_l:
max_l = height[left]
else:
water += max_l - height[left] # never negative: max_l > height[left]
left += 1
else:
if height[right] >= max_r:
max_r = height[right]
else:
water += max_r - height[right]
right -= 1
return water
# Edge cases
print(trap([])) # 0: empty
print(trap([1])) # 0: single bar
print(trap([1,2])) # 0: two bars
print(trap([3,0,3])) # 3: simple valley
print(trap([3,3,3])) # 0: flat top, no waterVerificação Rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da Lição
Nesta lição, você aprendeu: prender água da chuva consiste em encontrar o mínimo entre as paredes mais altas à esquerda e à direita de cada posição, a abordagem de dois ponteiros com espaço O(1) funciona porque o máximo acumulado do lado menor é sempre a restrição determinante e a abordagem da pilha monotônica calcula a água em camadas horizontais, sendo útil quando combinada com outra lógica baseada em pilha. A seguir, passaremos aos conceitos de arquitetura de sistemas, começando pela estrutura RADIO para respostas estruturadas em entrevistas.
Perguntas Frequentes
A aula “Acúmulo de água da chuva: pilha e dois ponteiros” é grátis?
Sim — o texto completo de “Acúmulo de água da chuva: pilha e dois ponteiros” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Acúmulo de água da chuva: pilha e dois ponteiros”?
Resolva o problema do acúmulo de água da chuva usando tanto a abordagem de pilha monotônica, que calcula camadas horizontais, quanto a abordagem de dois ponteiros, que calcula colunas verticais. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Acúmulo de água da chuva: pilha e dois ponteiros”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Pilha monotônica: crescente vs decrescente
- Maior retângulo no histograma
- Máximo em janela deslizante com deque monotônica
- Acúmulo de água da chuva: pilha e dois ponteiros