Exemplos práticos de Janela Deslizante (Sliding Window)

Exemplos Práticos de Janela Deslizante

A técnica de Janela Deslizante é amplamente usada para resolver problemas de forma eficiente, evitando cálculos redundantes. Vamos ver dois exemplos clássicos.

Exemplo 1: Soma Máxima de Subarray de Tamanho Fixo

Problema: Dado um array e um tamanho de janela k, encontre a soma máxima de qualquer subarray de tamanho k.

Dados:

• Array: [2, 1, 5, 1, 3, 2]
• k = 3

Passos:

1. Primeira janela (índices 0-2): [2, 1, 5] → Soma = 8
2. Desliza a janela: Remove o primeiro elemento (2) e adiciona o próximo (1). Nova janela: [1, 5, 1] → Soma = 7
3. Próxima janela: Remove 1, adiciona 3 → [5, 1, 3] → Soma = 9
4. Última janela: Remove 5, adiciona 2 → [1, 3, 2] → Soma = 6

Resultado: Soma máxima = 9 (janela [5, 1, 3]).

Exemplo 2: Substring Sem Caracteres Repetidos

Problema: Encontrar o comprimento da maior substring sem caracteres repetidos.

Dados:

• String: "abcabcbb"

Passos:

1. Inicia janela vazia e usa um conjunto (set) para caracteres únicos.
2. Expande a janela para a direita até encontrar repetição.
3. Quando encontra 'a' repetido, move o início da janela para a direita.
4. Continua até o final da string.

Resultado: Comprimento máximo = 3 (substring "abc").

Análise

• Eficiência: A janela deslizante reduz a complexidade de O(n²) para O(n) em muitos casos.
• Aplicações: Processamento de imagens, análise de séries temporais, redes de computadores.
• Vantagem: Evita recalcular somas ou verificações de cada subarray do zero.

Conclusão

A técnica é poderosa para problemas envolvendo subarrays ou substrings contíguas. Dominar a janela deslizante é essencial para otimizar algoritmos em provas e entrevistas.