Sliding Window Maximum
Você recebe um array de inteiros nums e um tamanho de janela k. Uma janela de k valores consecutivos começa na extremidade esquerda e se move uma posição para a direita de cada vez, até que sua extremidade direita fique sobre o último valor. Retorne o maior valor da janela em cada posição, da esquerda para a direita: n-k+1 valores para um array de comprimento n.
Função
- numsinteger-array
- a matriz sobre a qual a janela desliza
- kinteger
- o número de valores em cada janela
- Retornainteger-array
- o maior valor de cada janela, da janela mais à esquerda até a mais à direita
Restrições
1 ≤ k ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- O resultado contém
nums.length-k+1valores, um por janela, da esquerda para a direita.
Exemplos
- Entrada
- nums = [4, 2, 12, 3, 8, 5, 1]k = 3
- Saída
- [12, 12, 12, 8, 8]
- Explicação
- 12 está dentro das três primeiras janelas, então cada uma delas retorna 12. Depois que ele sai,
[3, 8, 5]e[8, 5, 1]têm 8 como seu maior valor.
- Entrada
- nums = [-3, -1, -7, -2]k = 2
- Saída
- [-1, -1, -2]
- Explicação
- As janelas são
[-3, -1],[-1, -7]e[-7, -2]. O maior de dois números negativos é aquele que está mais próximo de zero, o que resulta em -1, -1 e -2.
- Entrada
- nums = [6, 6, 1]k = 3
- Saída
- [6]
- Explicação
- Quando
ké igual ao comprimento do array, há uma janela: o array inteiro. Seu maior valor é 6; a segunda ocorrência de 6 não gera uma segunda resposta.
Para ir além
Você consegue criar uma fila que permita adicionar um valor no final, remover o valor da frente e ler seu máximo atual, cada operação em tempo amortizado O(1)?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Verificar cada janela em busca de seu maior valor custa
ketapas por janela. Compare duas janelas vizinhas: elas compartilhamk-1valores, porque um valor sai pela esquerda e outro entra pela direita.Quando um novo valor entra, nenhum valor mais antigo na janela que seja menor ou igual a ele poderá voltar a ser um máximo. O novo valor permanece em todas as janelas posteriores que ainda contêm o valor mais antigo, e é pelo menos tão grande quanto ele. Você pode descartar esses valores mais antigos de vez.
Mantenha os índices dos valores que permanecem em uma fila de duas pontas, com seus valores estritamente decrescentes da frente para trás. Para cada novo índice, remova do final os valores menores ou iguais, adicione o índice, remova o primeiro elemento se ele tiver saído da janela e leia o máximo da janela no início.
Solução
Janelas vizinhas compartilham k-1 valores, então recalcular cada máximo repete quase todo o trabalho. Mas não é possível desfazer um máximo: quando o maior valor sai da janela, você precisa do próximo maior sem ler a janela novamente. Uma deque monótona mantém apenas os valores que ainda podem se tornar um máximo, com a resposta na frente.
Examine todas as janelas
Correta, mas não termina nos maiores testes
Intuição
Leia os valores de k de cada janela e mantenha o maior. Cada janela é lida por completo, então seu máximo não pode passar despercebido. Cada uma das n-k+1 janelas custa k leituras, no pior caso quando k é aproximadamente metade de n: n = 2 × 10^4 e k = 10^4 resultam em cerca de 10^4 janelas de 10^4 valores, 10^8 leituras.
Algoritmo
- Faça um loop com
startde 0 atén-k. - Pegue o maior valor entre
nums[start]enums[start+k-1]. - Adicione-o ao resultado e retorne o resultado após o loop.
def maxSlidingWindow(nums, k):
result = []
for start in range(len(nums) - k + 1):
# Read all k values of this window again
result.append(max(nums[i] for i in range(start, start + k)))
return resultBlocos com máximos de cada lado
Intuição
Divida o array em blocos de k: índices de 0 a k-1, depois de k a 2k-1 e assim por diante, com um último bloco menor se k não dividir n. Uma janela tem exatamente k elementos, então ela corresponde a um bloco inteiro ou ao final de um bloco mais o início do próximo.
Assim, pré-calcule fromStart[i], o maior valor desde o início do bloco de i até i, e toEnd[i], o maior valor de i até o fim do bloco. A janela que começa em i termina em i+k-1: toEnd[i] cobre sua parte esquerda e fromStart[i+k-1], sua parte direita; portanto, o maior dos dois é o máximo da janela. No primeiro exemplo, a janela [2, 12, 3] usa toEnd[1] = 12 e fromStart[3] = 3, resultando em 12.
Três passagens levam tempo O(n), ao custo de dois arrays auxiliares de comprimento n e da necessidade de ter o array inteiro antes da primeira resposta.
Algoritmo
- Preencha
fromStartda esquerda para a direita, reiniciando comnums[i]quandoifor múltiplo dek. - Preencha
toEndda direita para a esquerda, reiniciando comnums[i]no último índice e sempre quei+1for múltiplo dek. - Para cada início
i, de 0 an-k, anexe o maior entretoEnd[i]efromStart[i+k-1].
def maxSlidingWindow(nums, k):
n = len(nums)
# Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
from_start = [0] * n # max from the start of i's block up to i
to_end = [0] * n # max from i up to the end of i's block
for i in range(n):
if i % k == 0:
from_start[i] = nums[i]
else:
from_start[i] = max(from_start[i - 1], nums[i])
for i in range(n - 1, -1, -1):
if i == n - 1 or (i + 1) % k == 0:
to_end[i] = nums[i]
else:
to_end[i] = max(to_end[i + 1], nums[i])
# A window [i, i+k-1] is the tail of one block plus the head of the next.
return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]Deque monotônica de índices
Intuição
Se o índice j vem antes de i e nums[j] ≤ nums[i], então j nunca mais poderá ser um máximo: toda janela posterior que contiver j também conterá i, que sai depois. Portanto, quando i chegar, você poderá esquecer j.
Mantenha um deque com os índices ainda não esquecidos. Quando i chegar, remova índices do final enquanto seus valores forem menores ou iguais a nums[i] e, em seguida, adicione i. Os valores restantes diminuem estritamente da frente para o final, então a frente é o máximo da janela. Armazene os índices, pois a frente também precisa sair quando a janela passar por ela. No primeiro exemplo, no índice 5, o deque contém 12, 8 e 5; 12 está no índice 5 - 3 = 2, então sai e a resposta é 8.
Cada índice é adicionado uma vez e removido no máximo uma vez: no máximo 2n operações de deque, tempo O(n). O deque nunca contém mais de k índices.
Algoritmo
- Para cada índice
i, remova índices do final enquanto o deque não estiver vazio e o valor no final for menor ou igual anums[i]. - Adicione
iao final. - Se o índice da frente for igual a
i-k, ele saiu da janela: remova-o. - Quando
i ≥ k-1, adicione o valor do índice da frente ao resultado.
from collections import deque
def maxSlidingWindow(nums, k):
window = deque() # indices; their values strictly decrease from front to back
result = []
for i, x in enumerate(nums):
# A value at the back that is not bigger than x can never be a maximum again.
while window and nums[window[-1]] <= x:
window.pop()
window.append(i)
# The front index has slid out of the window on the left.
if window[0] == i - k:
window.popleft()
# From index k-1 on, every step completes a window; its maximum sits at the front.
if i >= k - 1:
result.append(nums[window[0]])
return result
Armadilhas e casos extremos
- Armazenar valores em vez de índices. Com
[3, 1, 3]ek = 2, o segundo 3 remove o primeiro da fila e, em seguida, é removido também porque é igual anums[0], o valor que saiu. - Responder cedo ou tarde demais. A primeira janela completa termina no índice
k-1, e o resultado deve conter exatamenten-k+1valores. - Expirar
i-k+1em vez dei-k. Esse índice ainda corresponde ao primeiro valor da janela. - Ler o final da deque sem verificar se ela contém algum elemento.
- Na abordagem por blocos, esquecer que o último bloco pode ser menor que
k. A passagem da direita para a esquerda também deve recomeçar no último índice, além de em cada final de bloco.
Perguntas frequentes3
Qual é a complexidade de tempo do máximo da janela deslizante?
A solução com deque monotônico é executada em tempo O(n), porque cada índice é inserido uma vez e removido no máximo uma vez. O deque contém no máximo k índices, então o espaço extra é O(k), além do espaço ocupado pelo resultado.
O máximo em uma janela deslizante pode ser resolvido com um heap?
Sim. Insira pares de valor e índice em um heap máximo e, antes de ler o topo, remova o elemento do topo enquanto o índice dele estiver fora da janela. Isso leva O(n log n) de tempo e pode armazenar até n entradas. A deque é mais rápida e menor porque descarta valores inúteis assim que um maior chega.
Qual é a diferença entre uma deque monotônica e uma pilha monotônica?
A parte de trás do deque funciona como uma pilha monótona: antes de inserir um valor, você remove os valores que ele torna inúteis. O deque adiciona uma saída pela frente para os valores que estão velhos demais. O próximo elemento maior não tem prazo de validade, então precisa apenas da pilha. Inverta a comparação e o deque fornece o mínimo de cada janela.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def maxSlidingWindow(nums, k):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
Saída Esperada
[12, 12, 12, 8, 8]