Máximo de ventana deslizante con deque
Mantenga los extremos de la ventana en O(n)
Máximo de ventana deslizante con deque es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
El máximo de una ventana deslizante
Dado un arreglo y un tamaño de ventana k, quiere obtener el máximo de cada ventana mientras se desliza hacia la derecha. Hacerlo de forma ingenua cuesta O(n por k).
Una promesa más rápida
Con una deque monótona puede responder para cada ventana en un tiempo total O(n), recorriendo el arreglo una sola vez.
Guardar índices de nuevo
Guarde índices en la deque, no valores. Los índices permiten comprobar si el elemento del frente ya salió de la ventana actual.
from collections import deque
dq = deque()
res = []Mantener el orden decreciente
La deque mantiene los valores en orden decreciente desde el frente hasta el final, por lo que el índice del frente siempre señala el máximo de la ventana.
Eliminar los menores del final
Antes de añadir el índice i, elimine elementos del final mientras sus valores sean menores, ya que nunca podrán ser un máximo futuro.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()Añadir el índice nuevo
Después de eliminar los elementos más débiles del final, use append para añadir el índice actual. El orden de la deque seguirá siendo correcto para los pasos siguientes.
dq.append(i)Expulsar el frente obsoleto
Si el índice del frente queda fuera de la ventana, elimínelo con popleft. Una ventana de tamaño k comienza en el índice i menos k más uno.
if dq[0] <= i - k:
dq.popleft()Registrar cada máximo
Cuando se forma la primera ventana completa en el índice k menos uno, el frente de la deque contiene la respuesta para todas las posiciones siguientes.
if i >= k - 1:
res.append(nums[dq[0]])Cuidar el orden de expulsión
Expulse el frente obsoleto antes de leer la respuesta. De lo contrario, podría informar de un máximo que ya salió de la ventana.
Por qué el tiempo es lineal
Cada índice se añade y se elimina como máximo una vez, por lo que el trabajo de la deque es amortizado O(1) por paso y O(n) en total.
Mínimo de ventana, la misma idea
Para obtener el mínimo de una ventana deslizante, mantenga la deque en orden creciente. Solo tiene que invertir la comparación al recortar el final.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()Comprobación rápida
En el máximo de una ventana deslizante, ¿qué contiene el frente de la deque monótona?
Resumen: la deque gana en las ventanas
Ha mantenido una deque decreciente de índices: recorte los elementos menores del final, expulse el frente obsoleto y lea el frente para obtener el máximo de cada ventana en O(n). 🏆
Preguntas frecuentes
¿La lección «Máximo de ventana deslizante con deque» es gratis?
Sí — el texto completo de «Máximo de ventana deslizante con deque» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Máximo de ventana deslizante con deque»?
Mantenga los extremos de la ventana en O(n) Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Máximo de ventana deslizante con deque»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Pilas para emparejar corchetes
- Pila monótona: siguiente elemento mayor
- Colas y collections.deque
- Máximo de ventana deslizante con deque