Sliding Window Maximum
Recibes un arreglo de enteros nums y un tamaño de ventana k. Una ventana cubre k valores consecutivos. Empieza en el extremo izquierdo del arreglo y avanza una posición hacia la derecha cada vez, hasta que su borde derecho queda sobre el último valor.
Devuelve un arreglo con el valor más grande dentro de la ventana en cada una de sus posiciones, de izquierda a derecha. Un arreglo de longitud n tiene n-k+1 ventanas, por lo que el resultado tiene n-k+1 valores.
Función
- numsinteger-array
- el arreglo sobre el que se desliza la ventana
- kinteger
- la cantidad de valores en cada ventana
- Devuelveinteger-array
- el valor más grande de cada ventana, de la ventana más a la izquierda a la más a la derecha
Restricciones
1 ≤ k ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- El resultado contiene
nums.length-k+1valores, uno por ventana, en orden de izquierda a derecha.
Ejemplos
- Entrada
- nums = [4, 2, 12, 3, 8, 5, 1]k = 3
- Salida
- [12, 12, 12, 8, 8]
- Explicación
- 12 está dentro de las tres primeras ventanas,
[4, 2, 12],[2, 12, 3]y[12, 3, 8]. Después de que sale, las ventanas[3, 8, 5]y[8, 5, 1]tienen ambas 8 como su valor más grande.
- Entrada
- nums = [-3, -1, -7, -2]k = 2
- Salida
- [-1, -1, -2]
- Explicación
- Las ventanas son
[-3, -1],[-1, -7]y[-7, -2]. El mayor de dos números negativos es el que está más cerca de cero, lo que da -1, -1 y -2.
- Entrada
- nums = [6, 6, 1]k = 3
- Salida
- [6]
- Explicación
- Cuando
kes igual a la longitud del arreglo, hay una ventana: todo el arreglo. Su valor más grande es 6, y la segunda copia de 6 no añade una segunda respuesta.
+15 pruebas ocultas al enviar
Para ir más allá
¿Puedes construir una cola que permita añadir un valor al final, quitar el valor del principio y consultar su máximo actual, cada operación en tiempo amortizado O(1)?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Recorrer cada ventana para encontrar su valor más grande cuesta
kpasos por ventana. Compara dos ventanas vecinas: compartenk-1valores, porque un valor sale por la izquierda y otro entra por la derecha.Cuando entra un valor nuevo, ningún valor anterior de la ventana que sea menor o igual que él podrá volver a ser máximo. El valor nuevo permanece en todas las ventanas posteriores que aún contengan el valor anterior, y es al menos igual de grande. Puedes descartar definitivamente esos valores anteriores.
Conserva los índices de los valores que permanecen en una cola de doble extremo, con sus valores estrictamente decrecientes de principio a fin. Para cada índice nuevo, elimina del final los valores menores o iguales, añade el índice, elimina el primero si ha salido de la ventana y lee el máximo de la ventana al principio.
Solución
Las ventanas vecinas comparten k-1 valores, así que calcular cada máximo desde cero repite casi todo el trabajo. La parte difícil es que un máximo no se puede deshacer: cuando el valor más grande sale por la izquierda, necesitas el siguiente más grande sin volver a leer la ventana. Una deque monótona conserva exactamente los valores que todavía podrían llegar a ser máximos, en orden, así que la respuesta siempre está al frente y cada índice entra y sale de ella una vez.
Escanea todas las ventanas
Correcto, pero no termina con las pruebas más grandes
Intuición
La idea más directa se deduce de la afirmación. La ventana que empieza en el índice start abarca desde start hasta start+k-1. Lee esos k valores, conserva el mayor y mueve el inicio un paso a la derecha. Hay n-k+1 inicios, desde 0 hasta n-k.
Es correcto por definición: cada ventana se lee por completo, así que no se puede pasar por alto su valor más grande. La memoria adicional consiste en una variable para el máximo actual, aparte del resultado.
Es lento. Cada una de las n-k+1 ventanas requiere k lecturas, y el producto es mayor cuando k es aproximadamente la mitad de n. Con n = 2 × 10^4 y k = 10^4, son 10^4 ventanas de 10^4 valores, es decir, 10^8 lecturas. Y lo que es peor, dos ventanas contiguas comparten k-1 valores, así que casi todas las lecturas repiten un valor que ya habías leído.
Algoritmo
- Crea una lista de resultados vacía.
- Repite
startdesde 0 hastan-k. - Asigna
bestanums[start], después compáralo con cada valor hastanums[start+k-1]y conserva el mayor. - Añade
bestal resultado. - Devuelve el 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 resultBloques con máximos de cada lado
Intuición
Divide el array en bloques de k: índices del 0 al k-1, después del k al 2k-1, y así sucesivamente, con un último bloque más corto si n no es múltiplo de k. Una ventana tiene exactamente k elementos, así que coincide con un bloque o cubre el final de un bloque y el comienzo del siguiente. Nunca toca tres bloques.
Eso sugiere usar dos arrays. fromStart[i] es el valor máximo desde el comienzo del bloque de i hasta i; se completa de izquierda a derecha y se reinicia al comienzo de cada bloque. toEnd[i] es el valor máximo desde i hasta el final de su bloque; se completa de derecha a izquierda y se reinicia al final de cada bloque. La ventana que comienza en i termina en i+k-1. Su parte izquierda está cubierta por toEnd[i] y su parte derecha por fromStart[i+k-1], así que su máximo es el mayor de los dos. Cuando la ventana es un bloque completo, ambas partes tienen el máximo de ese bloque, y la respuesta sigue siendo correcta.
Con nums = [4, 2, 12, 3, 8, 5, 1] y k = 3, los bloques son [4, 2, 12], [3, 8, 5] y [1]. fromStart es [4, 4, 12, 3, 8, 8, 1] y toEnd es [12, 12, 12, 8, 8, 5, 1]. La ventana [2, 12, 3] comienza en 1: toEnd[1] = 12 cubre 2 y 12, fromStart[3] = 3 cubre 3, y la respuesta es 12.
Esto se ejecuta en tiempo O(n), con tres recorridos del array. El costo es usar dos arrays auxiliares de longitud n, y necesita el array completo antes de poder responder sobre la primera ventana.
Algoritmo
- Rellena
fromStartde izquierda a derecha: copianums[i]cuandoisea múltiplo dek; de lo contrario, toma el mayor defromStart[i-1]ynums[i]. - Rellena
toEndde derecha a izquierda: copianums[i]cuandoisea el último índice oi+1sea múltiplo dek; de lo contrario, toma el mayor detoEnd[i+1]ynums[i]. - Para cada inicio
idesde 0 hastan-k, añade el mayor detoEnd[i]yfromStart[i+k-1]. - Devuelve el 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)]Cola doble monótona de índices
Intuición
Parte de una observación. Supón que el índice j aparece antes que el índice i y que nums[j] ≤ nums[i]. Todas las ventanas posteriores que todavía contienen j también contienen i, porque i está más a la derecha y sale más tarde. En todas esas ventanas, nums[i] es al menos tan grande, así que j ya nunca podrá volver a ser el máximo. En cuanto llega i, j deja de ser útil y puedes olvidarte de él.
Mantén una cola de doble extremo con los índices que no has olvidado. Cuando llega i, saca índices del final mientras sus valores sean menores o iguales que nums[i], y luego añade i. Los índices que quedan tienen valores estrictamente decrecientes de principio a fin, ya que cualquier valor anterior que no fuera mayor se habría eliminado. Así que el primero contiene el valor más grande de la ventana. La deque almacena índices, no valores, porque el primero también tiene que salir cuando la ventana lo rebasa: la ventana que termina en i empieza en i-k+1, así que el índice i-k es el que ha salido de la ventana; si está al principio, lo eliminas.
Sigue nums = [4, 2, 12, 3, 8, 5, 1] con k = 3, anotando los valores de la deque. Entra 4: [4]. 2 es menor, así que se queda detrás: [4, 2]. 12 elimina ambos: [12], y la respuesta de la primera ventana es 12. 3 se queda esperando: [12, 3], respuesta 12. 8 elimina 3: [12, 8], respuesta 12. 5 se queda esperando: [12, 8, 5], pero 12 está en el índice 2, y la ventana que termina en el índice 5 empieza en el índice 3, así que 12 ha salido de la ventana: [8, 5], respuesta 8. 1 se queda esperando: [8, 5, 1], respuesta 8.
Por qué esto es O(n): el bucle interno puede eliminar varios índices en un paso, pero cada índice se añade una vez y se elimina como máximo una vez, desde el final cuando un valor mayor lo supera o desde el principio cuando sale de la ventana. Todas las eliminaciones del proceso completo suman como máximo n, así que el trabajo total es como máximo 2n operaciones de deque. Todos los índices de la deque están dentro de la ventana actual, así que nunca contiene más de k índices.
Algoritmo
- Crea un deque vacío para los índices y una lista de resultados vacía.
- Para cada índice
i, extrae índices del final mientras el deque no esté vacío y el valor de su último índice sea menor o igual quenums[i]. - Agrega
ial final. - Si el índice del frente es igual a
i-k, ha salido de la ventana: extráelo del frente. - Una vez que
i ≥ k-1, una ventana completa termina eni: agrega al resultado el valor del índice del frente. - Devuelve el 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
Errores comunes y casos límite
La mayoría de los errores provienen de los límites de la ventana o de lo que almacena la deque.
- Almacenar valores en lugar de índices. Después eliminas el frente cuando es igual a
nums[i-k], y los duplicados hacen que falle. Con[3, 1, 3]yk = 2, el segundo 3 expulsa al primero y luego él mismo se elimina, porque es igual al valor que salió. Almacena índices y compara el frente coni-k. - Dar la respuesta demasiado pronto o demasiado tarde. La primera ventana completa termina en el índice
k-1, no enk, y el resultado debe contener exactamenten-k+1valores. - Eliminar el índice equivocado. La ventana que termina en
iempieza eni-k+1, así quei-kes el índice que sale. Eliminari-k+1quita un valor que todavía está en la ventana. - Leer el final o el frente de una deque vacía. Comprueba que contenga algo antes de compararla con su final.
- Tratar la deque como una copia de la ventana. Solo contiene los candidatos, entre 1 y
kíndices, así que su tamaño no te dice nada sobre la ventana. - En el enfoque por bloques, olvidar que el último bloque puede ser más corto que
k. El recorrido de derecha a izquierda también debe reiniciarse en el último índice, además de en el final de cada bloque.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de Sliding Window Maximum?
La solución con una deque monótona se ejecuta en tiempo O(n). Cada índice se inserta una vez y se extrae como máximo una vez, así que el bucle interno realiza como máximo n extracciones en toda la ejecución, aunque un solo paso puede extraer varios elementos. La deque contiene como máximo k índices, por lo que el espacio adicional es O(k), además del espacio del resultado.
¿Se puede resolver el máximo de una ventana deslizante con un montón?
Sí. Inserta pares de valor e índice en un montículo máximo. Antes de leer el elemento superior, sácalo mientras su índice esté fuera de la ventana, ya que las entradas obsoletas solo se eliminan cuando llegan a la cima. Esto se ejecuta en O(n log n) y puede contener hasta n entradas. La deque es más rápida y pequeña porque elimina los valores inútiles en cuanto llega uno mayor.
¿Por qué la deque almacena índices y no valores?
El frente debe salir cuando la ventana avanza más allá de él, y solo su índice te lo indica. Con solo los valores, tendrías que deducirlo a partir de nums[i-k], lo cual falla cuando el mismo valor aparece más de una vez. El índice también te da el valor sin costo adicional, como en nums[index].
¿Cuál es la diferencia entre una cola monótona y una pila monótona?
La parte trasera del deque funciona como una pila monótona: antes de insertar un valor, eliminas los valores que vuelve inútiles. El deque añade una segunda salida al frente para los valores que son demasiado antiguos. Un problema sin caducidad, como encontrar el siguiente elemento mayor, solo necesita la pila; una ventana deslizante necesita ambos extremos. Invierte la comparación y el mismo código obtiene el mínimo de cada ventana.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def maxSlidingWindow(nums, k):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
Esperado
[12, 12, 12, 8, 8]