Sliding Window (Dynamic)
Quando o problema não te dá o tamanho da janela, é ele que você procura. A direita sempre avança; a esquerda só encolhe enquanto a janela está inválida.
Quando o tamanho não é dado
Na versão fixa, a janela sempre tinha k elementos. Aqui o tamanho varia: o enunciado define quando uma janela é válida (soma ≤ k, no máximo um zero, produto < k, caracteres sem repetir…) e pede a maior, ou a menor, janela válida.
A mecânica é sempre a mesma:
- Cresça pela direita sempre, adicionando
nums[direita]à métrica. - Encolha pela esquerda enquanto a janela for inválida, removendo
nums[esquerda]. - Atualize a resposta quando a janela estiver válida.
A ideia, em uma frase
Rode o visualizador: a métrica é a soma, a restrição é soma ≤ k, e a resposta é o maior tamanho de janela válida. Aperte Expandir para ler o código lado a lado.
Janela vazia. esquerda e direita começam em 0.
Por que dá para descartar o que saiu
Com números positivos, remover um elemento da esquerda só diminui a soma, nunca a aumenta. Então, quando a janela estoura k, encolher pela esquerda é a única forma de voltar a valer, e o elemento que saiu nunca mais vai ajudar (qualquer janela futura que o contivesse seria ainda maior). É esse argumento que garante que cada ponteiro percorre o array uma única vez: O(n) no total.
Cuidado com números negativos. Toda essa lógica depende de "encolher só melhora". Com valores negativos, uma janela maior pode ter soma menor, e o padrão quebra, nesse caso o caminho costuma ser soma de prefixos com hashmap.
Vídeo da aula
Direto do canal da comunidade Craft & Code Club · 18:24.
Problemas para praticar
Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.
Travou em algum passo? Traga sua questão para o Discord da comunidade ou para os encontros semanais.
Entrar