Sliding Window Maximum
Você recebe um array de números inteiros nums e um tamanho de janela k. Uma janela cobre k valores consecutivos. Ela começa na extremidade esquerda do array e se move uma posição para a direita de cada vez, até que sua extremidade direita fique sobre o último valor.
Retorne um array com o maior valor dentro da janela em cada uma de suas posições, da esquerda para a direita. Um array de comprimento n tem n-k+1 janelas, então o resultado tem n-k+1 valores.
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, em ordem 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á nas três primeiras janelas,
[4, 2, 12],[2, 12, 3]e[12, 3, 8]. Depois que ele sai da janela, as janelas[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 entre 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, e a segunda ocorrência de 6 não acrescenta uma segunda resposta.
+15 testes ocultos ao enviar
Para ir além
Você consegue criar uma fila que permita adicionar um valor no final, remover o valor do início e consultar seu máximo atual, cada operação em tempo amortizado O(1)?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Examinar cada janela para encontrar 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, todo valor mais antigo na janela que seja menor ou igual a ele nunca mais poderá ser um máximo. O novo valor permanece em todas as janelas posteriores que ainda contenham 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 extremidades, com valores estritamente decrescentes da frente para trás. Para cada novo índice, remova do final os valores menores ou iguais, insira o índice, remova o primeiro elemento se ele tiver saído da janela e leia o máximo da janela na frente.
Solução
Janelas vizinhas compartilham k-1 valores, então calcular cada máximo do zero repete quase todo o trabalho. A parte difícil é que não é possível desfazer um máximo: quando o maior valor sai pela esquerda, você precisa do próximo maior sem ler a janela novamente. Uma deque monotônica mantém exatamente os valores que ainda poderiam se tornar um máximo, em ordem, de modo que a resposta está sempre na sua frente e cada índice entra e sai dela uma vez.
Examine cada janela
Correta, mas não termina nos maiores testes
Intuição
A ideia mais direta vem da definição. A janela que começa no índice start cobre de start a start+k-1. Leia esses k valores, mantenha o maior e mova o início uma posição para a direita. Há n-k+1 posições iniciais, de 0 a n-k.
Está correto por definição: cada janela é lida por inteiro, então seu maior valor não pode passar despercebido. A memória extra é uma variável para o máximo atual, além do resultado.
É lento. Cada uma das n-k+1 janelas custa k leituras, e o produto é maior quando k é aproximadamente metade de n. Com n = 2 × 10^4 e k = 10^4, são 10^4 janelas de 10^4 valores, ou 10^8 leituras. Pior ainda, duas janelas vizinhas compartilham k-1 valores, então quase toda leitura repete uma que você já fez.
Algoritmo
- Crie uma lista de resultados vazia.
- Percorra
startde 0 atén-k. - Defina
bestcomonums[start], depois compare-o com cada valor aténums[start+k-1]e mantenha o maior. - Adicione
bestao resultado. - Retorne o resultado.
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 n não for múltiplo de k. Uma janela tem exatamente k elementos, então ela corresponde a um bloco ou cobre o final de um bloco e o início do próximo. Ela nunca toca em três blocos.
Isso sugere dois arrays. fromStart[i] é o maior valor do início do bloco de i até i, preenchido da esquerda para a direita e reiniciado no início de cada bloco. toEnd[i] é o maior valor de i até o final do bloco, preenchido da direita para a esquerda e reiniciado no final de cada bloco. A janela que começa em i termina em i+k-1. Sua parte esquerda é coberta por toEnd[i] e sua parte direita por fromStart[i+k-1], então seu máximo é o maior dos dois. Quando a janela corresponde a um bloco inteiro, as duas partes têm o máximo desse bloco, e a resposta continua correta.
Com nums = [4, 2, 12, 3, 8, 5, 1] e k = 3, os blocos são [4, 2, 12], [3, 8, 5] e [1]. fromStart é [4, 4, 12, 3, 8, 8, 1] e toEnd é [12, 12, 12, 8, 8, 5, 1]. A janela [2, 12, 3] começa em 1: toEnd[1] = 12 cobre 2 e 12, fromStart[3] = 3 cobre 3, e a resposta é 12.
Isso leva O(n) de tempo, com três passagens pelo array. O custo são dois arrays auxiliares de comprimento n, e é necessário ter o array inteiro antes de responder à primeira janela.
Algoritmo
- Preencha
fromStartda esquerda para a direita: copienums[i]quandoifor múltiplo dek; caso contrário, escolha o maior entrefromStart[i-1]enums[i]. - Preencha
toEndda direita para a esquerda: copienums[i]quandoifor o último índice oui+1for múltiplo dek; caso contrário, escolha o maior entretoEnd[i+1]enums[i]. - Para cada início
i, de 0 an-k, adicione o maior entretoEnd[i]efromStart[i+k-1]. - Retorne o resultado.
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
Comece com uma observação. Suponha que o índice j venha antes do índice i e que nums[j] ≤ nums[i]. Toda janela posterior que ainda contém j também contém i, porque i está mais à direita e sai mais tarde. Em todas essas janelas, nums[i] é pelo menos tão grande, então j nunca mais poderá ser o máximo. No momento em que i chega, j não serve para nada, e você pode esquecê-lo.
Mantenha uma fila de duas pontas com os índices que você ainda não esqueceu. Quando i chega, remova índices do final enquanto seus valores forem menores ou iguais a nums[i] e, em seguida, insira i. Os índices restantes terão então valores estritamente decrescentes da frente para o final, pois qualquer valor mais antigo que não fosse maior teria sido removido. Portanto, a frente contém o maior valor da janela. O deque armazena índices, não valores, porque o índice da frente também precisa sair quando a janela passa por ele: a janela que termina em i começa em i-k+1, então o índice i-k é o que saiu da janela e, se estiver na frente, você o remove.
Acompanhe nums = [4, 2, 12, 3, 8, 5, 1] com k = 3, listando os valores no deque. 4 entra: [4]. 2 é menor, então fica atrás dele: [4, 2]. 12 remove ambos: [12], e a resposta para a primeira janela é 12. 3 fica esperando: [12, 3], resposta 12. 8 remove 3: [12, 8], resposta 12. 5 fica esperando: [12, 8, 5], mas 12 está no índice 2, e a janela que termina no índice 5 começa no índice 3, então 12 saiu da janela: [8, 5], resposta 8. 1 fica esperando: [8, 5, 1], resposta 8.
Por que isso é O(n): o loop interno pode remover vários índices em uma etapa, mas cada índice é inserido uma vez e removido no máximo uma vez, do final quando um valor maior o supera ou da frente quando ele sai da janela. Todas as remoções da execução inteira somam no máximo n, então o trabalho total é de no máximo 2n operações de deque. Todo índice no deque está dentro da janela atual, portanto ele nunca contém mais de k índices.
Algoritmo
- Crie um deque vazio para os índices e uma lista de resultados vazia.
- 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 no início for igual a
i-k, ele saiu da janela: remova-o do início. - Quando
i ≥ k-1, uma janela completa termina emi: adicione ao resultado o valor no índice do início. - Retorne o 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
A maioria dos bugs vem das bordas da janela ou daquilo que o deque armazena.
- Armazenar valores em vez de índices. Então, você remove o primeiro elemento quando ele é igual a
nums[i-k], e os valores duplicados causam problemas. Com[3, 1, 3]ek = 2, o segundo 3 remove o primeiro e depois é removido, pois é igual ao valor que saiu. Armazene índices e compare o primeiro comi-k. - Responder cedo ou tarde demais. A primeira janela completa termina no índice
k-1, não emk, e o resultado deve conter exatamenten-k+1valores. - Remover o índice errado. A janela que termina em
icomeça emi-k+1, entãoi-ké o índice que sai. Removeri-k+1elimina um valor que ainda está na janela. - Ler o último ou o primeiro elemento de um deque vazio. Verifique se há algo nele antes de comparar com o último elemento.
- Tratar o deque como uma cópia da janela. Ele contém apenas os candidatos, de 1 a
kíndices, então seu tamanho não informa nada sobre o tamanho da janela. - 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 recomeçar no fim de cada bloco.
Perguntas frequentes4
Qual é a complexidade de tempo do máximo da janela deslizante?
A solução com deque monótona é executada em tempo O(n). Cada índice é inserido uma vez e removido no máximo uma vez, então o loop interno faz no máximo n remoções durante toda a execução, embora uma única etapa possa remover vários índices. O deque contém no máximo k índices, então o espaço extra é O(k), além do resultado.
O problema Sliding Window Maximum pode ser resolvido com um heap?
Sim. Insira pares de valor e índice em um heap máximo. Antes de ler o topo, remova-o enquanto o índice estiver fora da janela, já que as entradas obsoletas só são removidas quando chegam ao topo. Isso leva O(n log n) e pode armazenar até n entradas. O deque é mais rápido e ocupa menos espaço porque remove os valores inúteis assim que um maior chega.
Por que o deque armazena índices e não valores?
A frente deve sair quando a janela passar por ela, e somente seu índice informa isso. Com apenas os valores, você teria que adivinhar usando nums[i-k], o que falha quando o mesmo valor aparece mais de uma vez. O índice também fornece o valor sem custo adicional, como em nums[index].
Qual é a diferença entre uma deque monotônica e uma pilha monotônica?
A parte de trás da deque funciona como uma pilha monotônica: antes de inserir um valor, você remove os valores que ele torna inúteis. A deque adiciona uma segunda saída na frente para os valores que estão velhos demais. Um problema sem expiração, como encontrar o próximo elemento maior, precisa apenas da pilha; uma janela deslizante precisa das duas extremidades. Inverta a comparação e o mesmo código 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.
Python
def maxSlidingWindow(nums, k):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
Esperado
[12, 12, 12, 8, 8]