24 de Março
Melhor hora para comprar e vender ação
Como sair da comparação de todos os pares e perceber que o problema só pede o menor preco até agora.
Arrays e Passada Unica Iniciante 15 min TypeScript
Dado um array prices, onde prices[i] e o preco de uma ação no dia i, retorne o lucro máximo que você pode obter comprando em um dia e vendendo em um dia posterior.
Se nenhum lucro for possível, retorne 0.
Exemplo:
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Compre no preco 1 e venda no preco 6.
O que perceber antes de codar
- A compra precisa acontecer antes da venda.
- O problema pede o melhor lucro, não a lista completa de operações.
- Se o preco só cai, a resposta e `0`, não um número negativo.
Erros comuns
- escolher o menor preco global mesmo que ele venha depois do dia de venda
- retornar prejuizo negativo quando o problema pede `0`
Passo 1 — Ler a restrição mais importante
O lucro e venda - compra.
Mas nem toda combinação vale.
A compra precisa acontecer antes da venda.
Isso elimina uma leitura errada bem comum: pegar o menor preco do array inteiro e o maior preco do array inteiro sem respeitar a ordem.
Passo 2 — Escrever a versão inicial correta
A primeira versão certa compara cada dia de compra com todos os dias de venda depois dele:
export function maxProfit(prices: number[]): number {
let bestProfit = 0
for (let buyDay = 0; buyDay < prices.length; buyDay += 1) {
for (let sellDay = buyDay + 1; sellDay < prices.length; sellDay += 1) {
bestProfit = Math.max(bestProfit, prices[sellDay] - prices[buyDay])
}
}
return bestProfit
}
Funciona. Mas percorre o resto do array de novo para cada dia.
Passo 3 — Perguntar o que o dia atual precisa saber
Quando você chega no preco de hoje, precisa lembrar de todos os dias anteriores?
Não.
Para calcular o melhor lucro vendendo hoje, só importa uma coisa:
qual foi o menor preco que eu vi até agora?
Se você souber isso, o lucro candidato do dia vira:
lucro = precoAtual - menorPrecoAteAgora
Passo 4 — Atualizar duas informações durante uma passada O(n)
Durante uma unica passada:
- mantenha o menor preco visto até agora
- calcule o lucro candidato de hoje
- atualize o melhor lucro encontrado
O problema inteiro cabe nisso.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function maxProfit(prices: 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 — Força bruta O(n²)
Compare cada dia de compra com todos os dias de venda depois dele.
export function maxProfit(prices: number[]): number {
let bestProfit = 0
for (let buyDay = 0; buyDay < prices.length; buyDay += 1) {
for (let sellDay = buyDay + 1; sellDay < prices.length; sellDay += 1) {
bestProfit = Math.max(bestProfit, prices[sellDay] - prices[buyDay])
}
}
return bestProfit
}Correta, mas lenta porque repete comparações demais.
Solução 2 — Passada unica O(n)
Se o dia atual só precisa do menor preco já visto, guarde só isso.
export function maxProfit(prices: number[]): number {
let minPrice = Infinity
let bestProfit = 0
for (const price of prices) {
minPrice = Math.min(minPrice, price)
bestProfit = Math.max(bestProfit, price - minPrice)
}
return bestProfit
}Você anda uma vez pelo array e mantem exatamente as duas informações que importam.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial compara cada compra com cada venda posterior e custa
O(n²). Mas, para cada dia, eu não preciso lembrar de todos os precos anteriores. Eu só preciso do menor preco até agora. Com isso, calculo o lucro candidato emO(1)por dia e resolvo em uma passada.
Isso mostra que você:
- respeitou a restrição de ordem
- identificou a informação mínima necessária
- justificou a otimização sem pular etapas
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- manter um melhor valor visto até agora
- atualizar resposta enquanto percorre
- decidir com base em estado acumulado simples
- evitar estrutura extra quando duas variaveis bastam
O ponto não e decorar esse problema.
O ponto e perceber quando a entrada pode ser resolvida com memória acumulada durante a passada.