Sliding Window Maximum

Q: ¿Cuál es la complejidad temporal del máximo de ventana deslizante?

La solución con una deque monótona se ejecuta en tiempo O(n) , porque cada índice se agrega una vez y se elimina como máximo una vez. La deque contiene como máximo k índices, así que el espacio adicional es O(k) , además del resultado.

DifícilVentana deslizante Pila monótona Cola

+10

Recibes un arreglo de enteros nums y un tamaño de ventana k. Una ventana de k valores consecutivos comienza en el extremo izquierdo y se desplaza una posición hacia la derecha cada vez, hasta que su borde derecho queda sobre el último valor. Devuelve el valor más grande de la ventana en cada posición, de izquierda a derecha: n-k+1 valores para un arreglo de longitud n.

Función

maxSlidingWindow(nums: integer-array, k: integer) → integer-array

numsinteger-array: el arreglo sobre el que se desliza la ventana
kinteger: el número de valores en cada ventana
Devuelveinteger-array: el valor más grande de cada ventana, desde la ventana más a la izquierda hasta la más a la derecha

Restricciones

1 ≤ k ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
El resultado contiene nums.length-k+1 valores, uno por ventana, 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 primeras tres ventanas, así que cada una devuelve 12. Después de que se desliza hacia afuera, [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 k es igual a la longitud del arreglo, hay una ventana: todo el arreglo. Su valor más grande es 6; la segunda copia de 6 no añade una segunda respuesta.

Para ir más allá

¿Puedes construir una cola que permita añadir un valor al final, eliminar el valor del frente y consultar su máximo actual, cada una en tiempo amortizado O(1)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Las ventanas adyacentes comparten k-1 valores, así que volver a calcular cada máximo repite casi todo el trabajo. Pero un máximo no se puede deshacer: cuando el valor más grande sale de la ventana, necesitas el siguiente más grande sin volver a leerla. Una deque monótona conserva solo los valores que todavía podrían convertirse en un máximo, y la respuesta está al frente.

Escanea cada ventana

Correcto, pero no termina con las pruebas más grandes

Intuición

Lee los valores k de cada ventana y conserva el mayor. Cada ventana se lee completa, así que no se puede pasar por alto su máximo. Cada una de las n-k+1 ventanas requiere k lecturas; el peor caso se da cuando k es aproximadamente la mitad de n: n = 2 × 10^4 y k = 10^4 dan unas 10^4 ventanas de 10^4 valores, 10^8 lecturas.

Algoritmo

Recorre start desde 0 hasta n-k.
Toma el mayor valor entre nums[start] y nums[start+k-1].
Añádelo al resultado y devuelve el resultado después del bucle.

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 result

Bloques 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 k no divide a n. Una ventana tiene exactamente una longitud de k, así que es un bloque entero o el final de un bloque más el inicio del siguiente.

Así que precalcula fromStart[i], el valor más grande desde el inicio del bloque de i hasta i, y toEnd[i], el valor más grande desde i hasta el final de su bloque. La ventana que empieza en i termina en i+k-1: toEnd[i] cubre su parte izquierda y fromStart[i+k-1] su parte derecha, así que el mayor de los dos es su máximo. En el primer ejemplo, la ventana [2, 12, 3] toma toEnd[1] = 12 y fromStart[3] = 3, lo que da 12.

Tres recorridos dan un tiempo de O(n), a cambio de dos arrays auxiliares de longitud n y de necesitar el array completo antes de la primera respuesta.

Algoritmo

Rellena fromStart de izquierda a derecha, reiniciando con nums[i] cuando i sea múltiplo de k.
Rellena toEnd de derecha a izquierda, reiniciando con nums[i] en el último índice y siempre que i+1 sea múltiplo de k.
Para cada inicio i desde 0 hasta n-k, agrega el mayor de toEnd[i] y fromStart[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 monótona de índices

Intuición

Si el índice j aparece antes que i y nums[j] ≤ nums[i], entonces j nunca podrá volver a ser un máximo: toda ventana posterior que contenga j también contiene i, que sale más tarde. Así que, cuando llega i, puedes descartar j.

Mantén una cola de doble extremo con los índices que aún no se han descartado. Cuando llega i, elimina índices por el final mientras sus valores sean menores o iguales que nums[i] y, después, añade i. Los valores restantes decrecen estrictamente de principio a fin, así que el primero es el máximo de la ventana. Guarda los índices, porque el primero también debe salir cuando la ventana lo sobrepase. En el primer ejemplo, en el índice 5 la cola contiene 12, 8 y 5; 12 está en el índice 5 - 3 = 2, así que sale y la respuesta es 8.

Cada índice se añade una vez y se elimina como máximo una vez: como máximo 2n operaciones de cola, en O(n) tiempo. La cola nunca contiene más de k índices.

Algoritmo

Para cada índice i, saca índices del final mientras la deque no esté vacía y el valor al final sea menor o igual que nums[i].
Inserta i al final.
Si el índice del frente es igual a i-k, ha salido de la ventana: sácalo.
Una vez que i ≥ k-1, añade al resultado el valor del índice del frente.

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

Guardar valores en lugar de índices. Con [3, 1, 3] y k = 2, el segundo 3 elimina el primero y luego se elimina a sí mismo porque es igual a nums[0], el valor que salió.
Responder demasiado pronto o demasiado tarde. La primera ventana completa termina en el índice k-1, y el resultado debe contener exactamente n-k+1 valores.
Eliminar i-k+1 en lugar de i-k. Ese índice todavía es el primer valor de la ventana.
Leer el final de la deque sin comprobar que contenga algo.
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 frecuentes3

¿Cuál es la complejidad temporal del máximo de ventana deslizante?

La solución con una deque monótona se ejecuta en tiempo O(n), porque cada índice se agrega una vez y se elimina como máximo una vez. La deque contiene como máximo k índices, así que el espacio adicional es O(k), además del resultado.

¿Se puede resolver el máximo de una ventana deslizante con un montículo?

Sí. Inserta pares de valor e índice en un montículo máximo y, antes de leer el elemento superior, extráelo mientras su índice esté fuera de la ventana. Esto se ejecuta en O(n log n) y puede contener hasta n entradas. La deque es más rápida y ocupa menos espacio porque descarta los valores inútiles en cuanto llega uno mayor.

¿Cuál es la diferencia entre una deque monótona y una pila monótona?

La parte trasera de la deque funciona como una pila monótona: antes de insertar un valor, eliminas los que vuelve inútiles. La deque añade una salida por el frente para los valores que son demasiado antiguos. El siguiente elemento mayor no tiene caducidad, así que solo necesita la pila. Invierte la comparación y la deque te da el mínimo de cada ventana.

def maxSlidingWindow(nums, k):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

nums = [4, 2, 12, 3, 8, 5, 1]
k = 3

Salida Esperada

[12, 12, 12, 8, 8]

Sliding Window Maximum

Función

Restricciones

Ejemplos

Pistas

Solución

Escanea cada ventana

Bloques con máximos de cada lado

Deque monótona de índices

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares