Monotonic Queue

O que e

Monotonic queue e uma fila mantida em ordem para que o melhor candidato da janela fique fácil de acessar.

Ela costuma guardar indices, não só valores.

Quando usar

Ela aparece muito quando o problema pede:

• máximo da janela
• mínimo da janela
• sliding window com consulta repetida de melhor elemento

Erro comum

O erro clássico e pensar “se existe queue, basta enfileirar tudo”.

Se você não remove quem ficou irrelevante, a fila perde o ganho.

Pergunta melhor

Antes de aplicar, vale perguntar:

1. a janela anda uma posição por vez?
2. eu preciso do melhor elemento da janela o tempo todo?
3. alguns elementos antigos já ficaram inutilmente piores que os novos?