24 de Março
Água da chuva acumulada
Como perceber que a agua em cada posição depende dos maximos dos dois lados e comprimir isso em dois ponteiros.
Arrays e Dois Ponteiros Avancado 28 min TypeScript
Dado um array height, onde cada valor representa a altura de uma barra, retorne quanta agua fica presa depois da chuva.
Exemplo:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
O que perceber antes de codar
- A agua de uma posição depende do menor entre o melhor muro da esquerda e o melhor muro da direita.
- Não existe agua negativa. Se a barra já for alta demais, a contribuicao daquela posição e zero.
- O desafio não e a formula. E descobrir quando um lado já esta decidido.
Erros comuns
- somar `min(leftMax, rightMax) - height[i]` sem limitar em zero
- mover ponteiros sem justificar qual lado já pode ser resolvido
Passo 1 - Entender a formula local
Em uma posição i, a agua acumulada e:
min(maxAEsquerda, maxADireita) - height[i]
Porque o nivel da agua só sobe até o menor dos dois muros que a seguram.
Passo 2 - Escrever a versão inicial mais direta
A versão inicial natural e:
- para cada indice
- procurar o maior valor a esquerda
- procurar o maior valor a direita
- calcular a contribuicao daquela posição
Funciona.
Mas repete muita busca.
Passo 3 - Perguntar o que realmente decide um lado
Se você mantem:
leftMaxcomo o maior valor visto da esquerdarightMaxcomo o maior valor visto da direita
entao, quando leftMax <= rightMax, o lado esquerdo já esta decidido.
O motivo e que, para a posição da esquerda atual, sempre existira um muro a direita pelo menos tao alto quanto leftMax.
Passo 4 - Transformar isso em dois ponteiros
Com dois ponteiros:
- se
leftMax <= rightMax, resolve a esquerda e avancaleft - senao, resolve a direita e recua
right
Assim, cada indice e processado uma vez.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function trap(height: number[]): number {
// sua solução aqui
return 0
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n)
Espaço: O(1)
Solução 1 - Escanear esquerda e direita para cada indice O(n²)
Boa versão inicial para tornar a formula concreta.
export function trap(height: number[]): number {
let water = 0
for (let index = 0; index < height.length; index += 1) {
let leftMax = 0
let rightMax = 0
for (let left = 0; left <= index; left += 1) {
leftMax = Math.max(leftMax, height[left])
}
for (let right = index; right < height.length; right += 1) {
rightMax = Math.max(rightMax, height[right])
}
water += Math.max(0, Math.min(leftMax, rightMax) - height[index])
}
return water
}Funciona, mas o mesmo máximo e recalculado várias vezes.
Solução 2 - Dois ponteiros com maximos acumulados em O(n)
Agora você resolve cada lado quando ele já esta decidido.
export function trap(height: number[]): number {
let left = 0
let right = height.length - 1
let leftMax = 0
let rightMax = 0
let water = 0
while (left < right) {
leftMax = Math.max(leftMax, height[left])
rightMax = Math.max(rightMax, height[right])
if (leftMax <= rightMax) {
water += leftMax - height[left]
left += 1
} else {
water += rightMax - height[right]
right -= 1
}
}
return water
}O insight forte e saber quando uma posição já pode ser fechada sem precisar conhecer o resto inteiro em detalhe.
O que dizer na entrevista
Uma explicação curta e boa seria:
A formula local e
min(leftMax, rightMax) - height[i]. A versão inicial recalcula esses maximos para cada indice. Na versão forte eu mantenholeftMaxerightMaxcom dois ponteiros. QuandoleftMax <= rightMax, o lado esquerdo já esta limitado e pode ser resolvido agora. O mesmo vale de forma simetrica para a direita.
Isso mostra que você:
- entende a formula da agua local
- justifica o movimento dos ponteiros
- explica por que a resposta de um lado já esta decidida
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- manter maximos acumulados dos dois lados
- decidir localmente quando um lado já esta resolvido
- usar
dois ponteiroscom invariantes mais fortes - comparar alternativas como arrays de prefixo,
pilhaedois ponteiros
O ponto não e decorar esse problema.
O ponto e aprender quando a informação parcial já basta para fechar um lado.