Máximo de ventana deslizante con deque monótona
Mantenga un deque decreciente de índices para responder consultas del máximo de una ventana en O(1) por elemento y resolver el problema sliding-window-maximum en O(n).
Máximo de ventana deslizante con deque monótona es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 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.
Problema del máximo en una ventana deslizante
El problema del máximo en una ventana deslizante (LeetCode 239) proporciona un arreglo y un tamaño de ventana k. A medida que la ventana se desplaza de izquierda a derecha, una posición cada vez, debe mostrar el elemento máximo de cada ventana. Un enfoque de fuerza bruta calcula el máximo de cada ventana de k elementos en O(k), lo que da un total de O(nk), demasiado lento para valores grandes de k.
La solución con un deque monótono (cola de doble extremo) logra O(n) en total manteniendo un deque decreciente de índices. El frente siempre contiene el índice del máximo de la ventana actual, lo que proporciona consultas del máximo en O(1) y permite operar tanto por el frente como por el final.
from collections import deque
# Brute force O(nk) for comparison
def sliding_max_brute(nums, k):
return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print('Input:', nums, 'k=', k)
print('Expected: [3, 3, 5, 5, 6, 7]')
print('Brute: ', sliding_max_brute(nums, k))Deque monótono: la idea clave
Mantenga un deque monótono decreciente que almacene índices, no valores. La invariante es: nums[deque[0]] >= nums[deque[1]] >= ... >= nums[deque[-1]]. Antes de añadir el índice i:
- Elimine los índices expirados del frente: si
deque[0] <= i - k, el índice ha salido de la ventana. - Elimine del final los índices con valores menores: mientras
nums[deque[-1]] <= nums[i], esos índices nunca podrán ser el máximo de una ventana futura (están más a la izquierda y tienen un valor menor), así que descártelos.
Después de estas operaciones, añada i al final. El frente siempre proporciona el máximo de la ventana actual.
from collections import deque
def sliding_window_max(nums, k):
dq = deque() # stores indices; values are decreasing
result = []
for i, n in enumerate(nums):
# 1. Remove indices outside the current window
while dq and dq[0] <= i - k:
dq.popleft()
# 2. Remove indices with smaller values from the back
while dq and nums[dq[-1]] <= n:
dq.pop()
dq.append(i)
# 3. Record max when first full window is complete
if i >= k - 1:
result.append(nums[dq[0]]) # front = max of current window
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3)) # [3, 3, 5, 5, 6, 7]Recorrido del deque paso a paso
Recorramos [1, 3, -1, -3, 5, 3, 6, 7] con k=3:
- i=0 (1): dq=[0]
- i=1 (3): pop 0 (1<3), dq=[1]
- i=2 (-1): -1<3, así que se conserva, dq=[1,2]. Ventana [1,3,-1], máximo=nums[1]=3
- i=3 (-3): -3<-1, dq=[1,2,3]. Compruebe el frente: 1 > 3-3=0, correcto. Máximo de la ventana=3
- i=4 (5): pop 3,2,1 (todos son menores), dq=[4]. El frente 4 > 4-3=1, correcto. Máximo=5
- i=5 (3): 3<5, dq=[4,5]. El frente 4 > 5-3=2, correcto. Máximo=5
- i=6 (6): pop 5,4 (ambos son menores), dq=[6]. Máximo=6
- i=7 (7): pop 6, dq=[7]. Máximo=7
from collections import deque
def sliding_window_max_trace(nums, k):
dq = deque()
result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
print(f' Remove expired index {dq[0]} from front')
dq.popleft()
while dq and nums[dq[-1]] <= n:
print(f' Remove smaller index {dq[-1]} (val={nums[dq[-1]]}) from back')
dq.pop()
dq.append(i)
print(f'i={i} n={n}: dq={list(dq)} vals={[nums[j] for j in dq]}')
if i >= k - 1:
win_max = nums[dq[0]]
result.append(win_max)
print(f' Window {nums[max(0,i-k+1):i+1]} -> max={win_max}')
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
result = sliding_window_max_trace(nums, 3)
print('Result:', result)Por qué cada elemento se inserta y se extrae como máximo una vez
La garantía de O(n) proviene del mismo argumento amortizado que en la pila monótona: cada índice se añade al deque exactamente una vez y se elimina como máximo una vez, ya sea por el frente cuando expira o por el final cuando otro índice lo sustituye. El número total de operaciones del deque en todo el bucle es como máximo 2n.
Los bucles while internos no aumentan la complejidad global: cualquier extracción realizada en ellos queda «pagada» por la inserción anterior. Este es el mismo razonamiento que se aplica a la pila monótona, extendido a un deque que permite eliminar elementos por ambos extremos.
from collections import deque
def sliding_window_max_instrumented(nums, k):
dq = deque()
result = []
front_pops = back_pops = pushes = 0
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft(); front_pops += 1
while dq and nums[dq[-1]] <= n:
dq.pop(); back_pops += 1
dq.append(i); pushes += 1
if i >= k - 1:
result.append(nums[dq[0]])
print(f'n={len(nums)}: pushes={pushes}, front_pops={front_pops}, back_pops={back_pops}')
print(f'Total deque ops = {pushes + front_pops + back_pops} <= 3n = {3*len(nums)}')
return result
import random; random.seed(0)
nums = [random.randint(-100, 100) for _ in range(20)]
sliding_window_max_instrumented(nums, 5)Mínimo en una ventana deslizante
El mínimo en una ventana deslizante es la contraparte simétrica: mantenga un deque monótono creciente (extraiga por el final cuando el elemento nuevo sea menor que el elemento del final). El frente siempre contiene el mínimo de la ventana actual. Todos los demás pasos son idénticos a los de la versión del máximo; solo debe invertir la dirección de la comparación.
Los problemas que piden el mínimo en una ventana deslizante suelen aparecer como subproblemas dentro de algoritmos más grandes. Por ejemplo, calcular el coste mínimo de trasladar mercancías a lo largo de una ruta con k paradas intermedias puede requerir el mínimo en una ventana deslizante sobre arreglos de DP.
from collections import deque
def sliding_window_min(nums, k):
dq = deque() # increasing monotonic deque
result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft() # expired
while dq and nums[dq[-1]] >= n:
dq.pop() # pop larger values from back
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]]) # front = min
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print('Max k=3:', sliding_window_min.__name__, '->', end=' ')
print(sliding_window_min(nums, 3)) # [-1, -3, -3, -3, 3, 3]
from collections import deque
def sliding_window_max(nums, k):
dq = deque(); result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i-k: dq.popleft()
while dq and nums[dq[-1]] <= n: dq.pop()
dq.append(i)
if i >= k-1: result.append(nums[dq[0]])
return result
print('Max k=3:', sliding_window_max(nums, 3)) # [3,3,5,5,6,7]Juego de saltos VI: DP con deque monótono
Juego de saltos VI (LeetCode 1696) es un ejemplo clásico de combinación de DP y un deque monótono. Dado un arreglo y un tamaño máximo de salto k, comenzando en el índice 0, en cada paso se salta entre 1 y k posiciones hacia delante y se suma la puntuación de la celda de destino. Maximice la puntuación total. La recurrencia de DP es dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]). Calcular el máximo en una ventana deslizante sobre el arreglo de DP proporciona un total de O(n).
Este patrón —una recurrencia de DP en la que cada celda depende del máximo de una ventana de tamaño fijo de celdas anteriores— aparece con frecuencia y siempre requiere un deque monótono.
from collections import deque
def max_result(nums, k):
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
dq = deque([0]) # indices of max dp values in current window
for i in range(1, n):
# Remove expired indices
while dq and dq[0] < i - k:
dq.popleft()
# dp[i] = nums[i] + max dp in window [i-k, i-1]
dp[i] = nums[i] + dp[dq[0]]
# Maintain decreasing deque on dp values
while dq and dp[dq[-1]] <= dp[i]:
dq.pop()
dq.append(i)
return dp[n - 1]
print(max_result([1,-1,-2,4,-7,3], 2)) # 7: path 1->4->3
print(max_result([10,-5,-2,4,0,3], 3)) # 17: path 10->4->3
print(max_result([1,-5,-20,4,-1,3,-6,-3], 2)) # 0Máximo en una ventana deslizante: alternativa del árbol de segmentos
Para problemas en los que el tamaño de la ventana varía (no es un k fijo), el deque monótono no se puede aplicar directamente. En su lugar, utilice una sparse table para consultas estáticas del máximo en rangos, en O(1) por consulta después de un preprocesamiento de O(n log n), o un árbol de segmentos para actualizaciones dinámicas, con O(log n) por consulta. Sin embargo, para ventanas deslizantes con k fijo, el deque es imbatible, con O(n).
En las entrevistas, prefiera siempre el deque monótono O(n) al árbol de segmentos O(n log n) cuando el tamaño de la ventana sea constante. Mencione la compensación: el deque no puede gestionar tamaños de ventana arbitrarios ni actualizaciones, mientras que los árboles de segmentos sí pueden.
# Sparse table for static RMQ (range maximum query)
import math
def build_sparse_table(arr):
n = len(arr)
LOG = int(math.log2(n)) + 1 if n else 1
table = [[0]*n for _ in range(LOG)]
table[0] = arr[:]
j = 1
while (1 << j) <= n:
for i in range(n - (1 << j) + 1):
table[j][i] = max(table[j-1][i], table[j-1][i + (1 << (j-1))])
j += 1
return table
def query(table, l, r):
k = int(math.log2(r - l + 1))
return max(table[k][l], table[k][r - (1 << k) + 1])
arr = [1, 3, -1, -3, 5, 3, 6, 7]
table = build_sparse_table(arr)
k = 3
result = [query(table, i, i + k - 1) for i in range(len(arr) - k + 1)]
print('Sparse table result:', result) # [3, 3, 5, 5, 6, 7]Subarreglo más largo de unos tras eliminar un elemento
LeetCode 1493: dado un arreglo binario, encuentre la longitud del subarreglo más largo compuesto por 1 después de eliminar exactamente un elemento, que puede ser un 0 o un 1. Este es un problema de ventana deslizante. Mantenga una ventana con como máximo un 0. Cuando la ventana tenga más de un 0, redúzcala desde la izquierda.
Este problema utiliza el patrón de ventana deslizante de tamaño variable, no un deque. Sin embargo, se combina con la técnica de máximo de la ventana: después de encontrar todas las ventanas válidas, la longitud máxima es la respuesta. «Eliminar un elemento» significa que permitimos exactamente un 0 en nuestra ventana de 1.
def longest_subarray(nums):
left = 0
zeros = 0
max_len = 0
for right in range(len(nums)):
if nums[right] == 0:
zeros += 1
while zeros > 1:
if nums[left] == 0:
zeros -= 1
left += 1
# Window [left, right] has at most 1 zero
# After deleting one element, length = right - left (not +1, since we delete one)
max_len = max(max_len, right - left)
return max_len
print(longest_subarray([1,1,0,1])) # 3: delete the 0
print(longest_subarray([0,1,1,1,0,1,1,0,1])) # 5
print(longest_subarray([1,1,1])) # 2: must delete one 1Comparación entre deque, cola y pila
Comprender cuándo utilizar cada contenedor es clave en las entrevistas:
- Pila (list): LIFO, acceso por un solo extremo. Úsela para DFS, análisis de expresiones y problemas de pilas monótonas.
- Cola (deque con appendleft/popleft): FIFO, inserción por un extremo y extracción por el otro. Úsela para BFS y planificación de tareas.
- Deque: acceso a ambos extremos en O(1). Úselo para ventanas deslizantes con expiración (eliminación por el frente) y una invariante monótona (eliminación por el final). El máximo en una ventana deslizante es el problema canónico de los deques.
El collections.deque de Python es la herramienta para los tres casos. Use append/pop para el comportamiento de pila y append/popleft o appendleft/pop para el comportamiento de cola o deque.
from collections import deque
# deque as stack
stack = deque()
stack.append(1); stack.append(2); stack.append(3)
print('Stack pop:', stack.pop()) # 3 (LIFO)
# deque as queue
queue = deque()
queue.append(1); queue.append(2); queue.append(3)
print('Queue pop:', queue.popleft()) # 1 (FIFO)
# deque as sliding window with front expiry + back monotonic
dq = deque()
nums = [3, 1, 4, 1, 5, 9, 2, 6]
k = 3
for i, n in enumerate(nums):
while dq and dq[0] <= i - k: dq.popleft() # expire front
while dq and nums[dq[-1]] <= n: dq.pop() # maintain back
dq.append(i)
if i >= k - 1:
print(f'Window {nums[max(0,i-k+1):i+1]}: max={nums[dq[0]]}')Subarreglo más corto con suma de al menos K: deque y sumas prefijas
Subarreglo más corto con suma de al menos K (LeetCode 862) es un problema avanzado que combina sumas prefijas con un deque monótono. Construya las sumas prefijas y, después, utilice un deque para encontrar, para cada extremo derecho, la suma prefija más a la izquierda que cumpla prefix[right] - prefix[left] >= k. El deque mantiene las sumas prefijas en orden creciente (extrae elementos del final para conservar dicho orden) y extrae elementos del frente para recopilar respuestas válidas.
Este es uno de los problemas más difíciles de ventanas deslizantes porque incluye números negativos (lo que descarta el enfoque sencillo de dos punteros) y requiere que el deque actúe tanto como estructura monótona como mecanismo de expiración.
from collections import deque
def shortest_subarray(nums, k):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
dq = deque() # monotonic increasing deque of indices into prefix
result = float('inf')
for right in range(n + 1):
# Pop from front: valid subarrays ending at `right`
while dq and prefix[right] - prefix[dq[0]] >= k:
result = min(result, right - dq.popleft())
# Pop from back: maintain increasing deque
while dq and prefix[dq[-1]] >= prefix[right]:
dq.pop()
dq.append(right)
return result if result != float('inf') else -1
print(shortest_subarray([1], 1)) # 1
print(shortest_subarray([1, 2], 4)) # -1
print(shortest_subarray([2, -1, 2], 3)) # 3
print(shortest_subarray([84,-37,32,40,95], 167)) # 3Estrategia de entrevista para problemas con deques
Identifique un problema de deque monótono mediante estas señales: (1) necesita el máximo o el mínimo de una ventana deslizante de tamaño fijo, (2) necesita una recurrencia de DP dp[i] = f(nums[i], max(dp[i-k..i-1])), o (3) necesita el índice válido más cercano que cumpla una condición monótona.
En las entrevistas, escriba la solución con deque de forma clara: importe deque, mantenga las dos invariantes (expiración por el frente y monotonicidad por el final) y devuelva los resultados a partir del índice k-1. Mencione siempre la complejidad temporal O(n) y el espacio O(k) del deque (se almacenan como máximo k índices a la vez), y compárela con la fuerza bruta O(nk) para mostrar la mejora.
from collections import deque
# Clean, interview-ready template
def sliding_window_max_template(nums, k):
if not nums or k == 0:
return []
dq = deque() # monotonic decreasing, stores indices
result = []
for i in range(len(nums)):
# Invariant 1: remove expired indices (outside window)
while dq and dq[0] < i - k + 1:
dq.popleft()
# Invariant 2: remove indices with smaller values (useless)
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# Record result once first full window is established
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Complexity: O(n) time, O(k) space
print(sliding_window_max_template([1,3,-1,-3,5,3,6,7], 3))
print(sliding_window_max_template([1], 1))
print(sliding_window_max_template([], 3))Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió que un deque monótono decreciente mantiene el máximo de la ventana en su frente y descarta por el final los elementos menores que las nuevas incorporaciones, que los índices expirados se eliminan del frente cuando quedan fuera del límite de la ventana, y que cada índice se inserta y se extrae como máximo una vez, lo que proporciona O(n) en total y un espacio O(k) para el deque. A continuación, resolveremos el problema de atrapar agua de lluvia utilizando tanto la pila monótona como el enfoque de dos punteros.
Preguntas frecuentes
¿La lección «Máximo de ventana deslizante con deque monótona» es gratis?
Sí — el texto completo de «Máximo de ventana deslizante con deque monótona» 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 monótona»?
Mantenga un deque decreciente de índices para responder consultas del máximo de una ventana en O(1) por elemento y resolver el problema sliding-window-maximum 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 3 de 4.
¿Cuánto tiempo toma la lección «Máximo de ventana deslizante con deque monótona»?
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
- Pila monótona: creciente frente a decreciente
- Rectángulo más grande en un histograma
- Máximo de ventana deslizante con deque monótona
- Trapping Rain Water: pila y dos punteros