Máximo em Janela Deslizante com Deque
Mantenha os extremos da janela em O(n).
Máximo em Janela Deslizante com Deque é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O máximo em uma janela deslizante
Dado um vetor e um tamanho de janela k, você quer o máximo de cada janela enquanto ela desliza para a direita. Fazer isso de maneira ingênua custa O(n vezes k).
Uma promessa mais rápida
Com um deque monótono, você pode responder a cada janela em tempo total O(n), percorrendo o vetor apenas uma vez.
Armazene índices novamente
Mantenha índices no deque, não valores. Os índices permitem verificar se o elemento da frente saiu da janela atual.
from collections import deque
dq = deque()
res = []Mantenha a ordem decrescente
O deque permanece decrescente por valor, da frente para trás. Assim, o índice da frente sempre aponta para o máximo da janela.
Remova as caudas menores
Antes de adicionar o índice i, remova pela parte de trás enquanto os values correspondentes forem menores, pois eles nunca poderão ser um máximo futuro.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()Adicione o novo índice
Depois de limpar as caudas mais fracas, use append para adicionar o índice atual. A ordem do deque continua correta para os próximos passos.
dq.append(i)Expulse a frente obsoleta
Se o índice da frente ficar fora da janela, use popleft para removê-lo. Uma janela de tamanho k começa no índice i menos k mais um.
if dq[0] <= i - k:
dq.popleft()Registre cada máximo
Quando a primeira janela completa se forma no índice k menos um, a frente do deque contém a resposta para todas as posições seguintes.
if i >= k - 1:
res.append(nums[dq[0]])Observe a ordem da expulsão
Remova a frente obsoleta antes de ler a resposta. Caso contrário, você poderá informar um máximo que já saiu da janela.
Por que o tempo linear se mantém
Cada índice é adicionado e removido no máximo uma vez. Portanto, o trabalho do deque custa O(1) amortizado por passo e O(n) no total.
Janela mínima, mesma ideia
Para obter o mínimo em uma janela deslizante, mantenha o deque crescente. Basta inverter a comparação ao aparar a parte de trás.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()Verificação rápida
No máximo de uma janela deslizante, o que a frente do deque monótono contém?
Recapitulação: o deque vence na janela
Você manteve um deque decrescente de índices: aparou as caudas pequenas, expulsou a frente obsoleta e leu a frente para obter o máximo de cada janela em O(n). 🏆
Perguntas Frequentes
A aula “Máximo em Janela Deslizante com Deque” é grátis?
Sim — o texto completo de “Máximo em Janela Deslizante com Deque” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Máximo em Janela Deslizante com Deque”?
Mantenha os extremos da janela em O(n). Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Máximo em Janela Deslizante com Deque”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Pilhas para Correspondência de Parênteses
- Pilha Monotônica: Próximo Elemento Maior
- Filas e collections.deque
- Máximo em Janela Deslizante com Deque