24 de Março
Container com mais água
Como justificar por que só faz sentido mover o lado menor e usar isso para reduzir a busca.
Arrays e Dois Ponteiros Intermediario 18 min TypeScript
Dado um array de inteiros height, onde cada valor representa a altura de uma linha vertical, encontre duas linhas que, junto com o eixo x, formem um container que armazena a maior quantidade de agua.
Retorne a area máxima.
Exemplo:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
O que perceber antes de codar
- A largura e a distancia entre os indices.
- A altura útil do container e o menor dos dois lados.
- O ponto difícil não e calcular area. E justificar qual ponteiro mover.
Erros comuns
- mover o ponteiro maior por intuição e não por argumento
- esquecer que a altura do container e limitada pelo menor lado
Passo 1 — Entender a formula da area
A area entre duas linhas e:
largura * alturaUtil
Onde:
largura = right - leftalturaUtil = min(height[left], height[right])
O menor lado manda.
Passo 2 — Escrever a versão inicial correta
A versão inicial compara toda dupla possível:
export function maxArea(height: number[]): number {
let best = 0
for (let left = 0; left < height.length; left += 1) {
for (let right = left + 1; right < height.length; right += 1) {
const width = right - left
const currentHeight = Math.min(height[left], height[right])
best = Math.max(best, width * currentHeight)
}
}
return best
}
Funciona. Mas não usa nenhuma estrutura do problema.
Passo 3 — Perguntar qual lado vale a pena mover
Se o lado esquerdo for menor, ele limita a area.
Se você mover o lado direito, a largura diminui e o lado limitante continua o mesmo.
Isso não tem como melhorar a area máxima daquele par base.
Entao, quando um lado e o limitante, só faz sentido tentar trocar esse lado.
Passo 4 — Usar dois ponteiros com descarte justificado
Comece com a maior largura possível:
leftno iníciorightno fim
Em cada passo:
- calcule a area
- mova o ponteiro da menor altura
- tente encontrar uma altura limitante melhor mesmo com largura menor
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function maxArea(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 — Testar todas as duplas
Serve como versão inicial, mas custa caro demais.
export function maxArea(height: number[]): number {
let best = 0
for (let left = 0; left < height.length; left += 1) {
for (let right = left + 1; right < height.length; right += 1) {
const width = right - left
const currentHeight = Math.min(height[left], height[right])
best = Math.max(best, width * currentHeight)
}
}
return best
}Solução 2 — Dois ponteiros com argumento guloso
Agora a busca anda só onde ainda existe chance real de melhora.
export function maxArea(height: number[]): number {
let left = 0
let right = height.length - 1
let best = 0
while (left < right) {
const width = right - left
const currentHeight = Math.min(height[left], height[right])
best = Math.max(best, width * currentHeight)
if (height[left] <= height[right]) {
left += 1
} else {
right -= 1
}
}
return best
}O valor aqui não e só chegar na resposta. E saber justificar o movimento.
O que dizer na entrevista
Uma explicação curta e boa seria:
A area depende da largura e do menor lado. Começo com a maior largura possível e, em cada passo, movo o ponteiro do lado menor. O motivo e que mover o lado maior não resolve o gargalo atual e ainda reduz a largura. Entao só o lado limitante pode abrir chance de melhora.
Isso mostra que você:
- entendeu o que realmente limita a area
- justificou a escolha
gulosa - transformou o algoritmo em argumento, não em template
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- comparar extremos
- mover só o lado que limita a resposta atual
- descartar busca com argumento de impossibilidade
- explicar por que uma escolha
gulosafaz sentido
O ponto não e decorar “move o menor”.
O ponto e justificar por que mover o maior não ajuda.