24 de Março
Monotonic Stack
O que monotonic stack significa, quando manter pilha em ordem ajuda a achar próximo maior ou menor sem loop duplo.
O que e
Monotonic stack e uma stack mantida em ordem.
Quando um novo elemento quebra essa ordem, você desempilha até restaurar a propriedade.
Quando usar
Ela costuma aparecer quando o problema pede:
- próximo maior
- próximo menor
- dias até temperatura maior
- spans
Erro comum
O erro clássico e olhar para ela como técnica exotica.
Na prática, e só uma forma organizada de dizer:
“alguns elementos antigos não importam mais depois que este chegou.”
Pergunta melhor
Antes de aplicar, vale perguntar:
- o problema compara cada elemento com vizinhos futuros ou passados?
- existe um grupo de elementos que perde relevância quando outro aparece?
- eu estou repetindo comparação demais em loop duplo?
Compartilhar esta página
Copie o link manualmente no campo abaixo.