Sesión 51: Cola de Doble Extremo Monótona (Monotonic Deque) & Sliding Window Maximum (LeetCode 239 Hard)#

Navegación rápida:

• ← Sesión 50: Trapping Rain Water (CTCI 17.21): Two Pointers vs Monotonic Stack
• Sesión 52: Árbol Binario Indexado (Fenwick Tree / BIT) y Prefijos Dinámicos →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 65-80 minutos.
• Código fuente compilado y probado: practica-rust/dia_51.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

En esta sesión estudiamos la estructura de datos que permite procesar ventanas deslizantes de tamaño dinámico o fijo en tiempo lineal estricto: el Monotonic Deque (Double-Ended Queue Monótona). Consulta el Glosario Maestro y la Guía de Diagramas.

Monotonic Deque (Cola de Doble Extremo Monótona)#

• (a) En palabras simples (intuición): Imagina la fila de candidatos a ser el empleado del mes en una empresa durante una ventana de tiempo. Cada vez que entra un candidato nuevo joven y talentoso, cualquier empleado veterano que haya trabajado menos que él y que además sea más viejo (va a jubilarse antes) queda descartado para siempre. Como el nuevo es más fuerte y durará más tiempo en la ventana, los más débiles ya no tienen ninguna posibilidad de ganar. En el frente de la fila siempre queda el mejor candidato absoluto.
• (b) Definición técnica paso a paso: Cola de doble extremo (VecDeque) que almacena índices de elementos asegurando que sus valores asociados mantengan un orden monótono estricto (decreciente para máximos o creciente para mínimos). En cada elemento nuevo en el índice i:

1. Expulsión por caducidad (Frente / pop_front): Se descartan índices que salieron del marco temporal de la ventana: front ≤ i - k.
2. Purga por dominancia (Cola / pop_back): Se expulsan por detrás todos los índices cuyo valor sea menor o igual al nuevo elemento (nums[back] ≤ nums[i]).
3. Inserción: Se añade i al final (push_back).
4. Consulta O(1): El elemento en el frente (deq.front()) es el máximo absoluto de la ventana.

• (c) Cómo funciona en Rust (memoria y tipos): Se implementa mediante std::collections::VecDeque<usize>, una estructura de buffer circular basada en un único vector contiguo en el Heap con punteros de lectura/escritura modulares.
• (d) Error típico de Junior: Almacenar los valores numéricos directos en el Deque en lugar de sus índices de posición; si guardas solo los valores, es imposible saber cuándo un elemento caducó y salió de la ventana deslizante.

Sliding Window Maximum (LeetCode 239 Hard)#

• (a) En palabras simples (intuición): Tienes un telescopio que enfoca exactamente k números contiguos a la vez en una cinta transportadora. La cinta avanza un casillero hacia la derecha en cada segundo. Debes anotar en un cuaderno cuál es el número más grande visible en el telescopio en cada segundo.
• (b) Definición técnica paso a paso: Problema de optimización sobre arreglos de tamaño N. Se computa max(nums[i - k + 1 … i]) para cada i ∈ [k - 1, N - 1].
• Fuerza bruta: O(N · k). Para N = 10⁵, k = 50,000 ⟹ 5 × 10⁹ operaciones (falla por TLE).
• Max-Heap con lazy deletion: O(N log k) tiempo y O(N) espacio.
• Monotonic Deque: O(N) tiempo lineal amortizado y O(k) espacio auxiliar óptimo.
• (c) Cómo funciona en Rust (memoria y tipos): El vector de resultados result se preasigna con Vec::with_capacity(n - k + 1), evitando realocaciones en el Heap.
• (d) Error típico de Junior: Usar una búsqueda lineal nums[i-k..=i].iter().max() dentro del bucle, convirtiendo el algoritmo en cuadrático O(N · k).

Amortized Analysis (Tiempo Amortizado por Elemento)#

• (a) En palabras simples (intuición): Compras un pase de temporada para el parque de diversiones. Pagas una sola vez y luego te subes a 50 juegos gratis. Si miras el costo de un día cualquiera, puede parecer caro o barato, pero si divides el gasto total entre todos los juegos a los que te subiste, cada atracción te costó centavos.
• (b) Definición técnica paso a paso: Método de análisis de complejidad algorítmica donde se evalúa el costo total de una secuencia de N operaciones en lugar de considerar el peor caso de una operación aislada. Aunque una iteración individual puede expulsar hasta k elementos en un bucle while, cada uno de los N elementos solo entra al Deque una vez y solo se expulsa como máximo una vez. El costo acumulado global es ≤ 2N, lo que otorga un costo promedio amortizado de O(1) por iteración.
• (c) Cómo funciona en Rust (memoria y tipos): Los accesos pop_back, pop_front, push_back en VecDeque se ejecutan en O(1) operaciones fijas de puntero.
• (d) Error típico de Junior: Ver un bucle while anidado dentro de un bucle for y concluir automáticamente que el tiempo es O(N²).

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

El Principio de Dominancia Temporal: ¿Por qué Descartar a los Menores?#

La genialidad del Monotonic Deque radica en el Principio de Inutilidad:

Consideremos dos índices j y i tales que j < i (el elemento j apareció antes en el arreglo que i). Supongamos que:

Preguntémonos: ¿Existe alguna ventana presente o futura donde nums[j] pueda ser el valor máximo?

1. En la ventana actual: nums[i] está presente, y como nums[i] ≥ nums[j], nums[j] no puede ser el máximo.
2. En cualquier ventana futura: Como la ventana se desliza hacia la derecha, el elemento j (que está más a la izquierda) caducará y saldrá de la ventana antes que i. Mientras j esté dentro de la ventana, i también lo estará obligatoriamente.
3. Conclusión: El elemento en la posición j jamás en toda la historia restante de la ejecución podrá ser el máximo de ninguna ventana.
4. Conservar j en memoria es un desperdicio absoluto de ciclos y espacio. Podemos expulsar a j de inmediato por la derecha (pop_back()) sin temor a equivocarnos.

Este descarte agresivo garantiza que la cola se mantenga estrictamente decreciente:

Traza Manual Detallada: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3#

Resultado final recolectado: [3, 3, 5, 5, 6, 7]. Observa que la cola nunca contuvo más de 3 elementos a la vez, garantizando O(k) de memoria física.

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama de Flujo: Inserción y Purga en Monotonic Deque#

Consulta el diagrama vectorial:

flowchart TD
    INPUT["Nuevo elemento: nums[i] en índice i"] --> POP_L{"¿deq.front() + k <= i?<br/>(¿Caducó de la ventana?)"}
    POP_L -->|Sí| DROP_L["deq.pop_front()<br/>(Desalojar elemento expirado)"]
    POP_L -->|No| POP_R
    DROP_L --> POP_R{"¿nums[deq.back()] <= nums[i]?<br/>(¿Elemento dominado?)"}
    POP_R -->|Sí| DROP_R["deq.pop_back()<br/>(Purgar candidato inferior)"]
    DROP_R --> POP_R
    POP_R -->|No| PUSH["deq.push_back(i)<br/>(Insertar nuevo índice)"]
    PUSH --> REC{"¿i + 1 >= k?<br/>(¿Ventana completa?)"}
    REC -->|Sí| COLLECT["result.push(nums[deq.front()])<br/>(Registrar máximo)"]
    REC -->|No| NEXT["Avanzar al siguiente i"]
    COLLECT --> NEXT

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Estructura interna de VecDeque<usize> como buffer circular en Heap durante el paso i = 4:

STACK:
[ deq: VecDeque { head: 0, len: 1, cap: 4 } ]
[ result: Vec { ptr: 0x8800_heap, len: 3, cap: 6 } ]

HEAP (Buffer Circular de VecDeque):
Dirección     Ranura    Valor (Índice de nums)
0x5000_deq    [0]       4   (apunta a nums[4] = 5)  <-- FRONT y BACK simultáneo
0x5000_deq    [1]       _   (elementos 1, 2, 3 fueron purgados)
0x5000_deq    [2]       _
0x5000_deq    [3]       _

OPERACIÓN EN MEMORIA:
1. head = 0, tail = 1.
2. Acceso a deq.front(): lectura directa de slot [head] en O(1) tiempo (sin indirecciones).
3. nums[4] = 5 se escribe en result[2].
Costo de memoria en Heap: exactamente 4 ranuras usize = 32 bytes para la cola.

4. Las 3 Trampas Clásicas en Entrevistas y Cómo Evitarlas#

Trampa 1: Usar < en Vez de <= en la Purga de Monotonicidad#

• El error: Escribir while nums[deq.back()] < nums[i].
• Por qué falla: Si hay elementos duplicados iguales (por ejemplo, [2, 2, 2, 2]), no purgar los iguales llena la cola innecesariamente de índices repetidos del mismo valor, desperdiciando memoria y ralentizando las consultas.
• La solución: Usar siempre <= para expulsar elementos menores o iguales:

  while let Some(&back) = deq.back() {
      if nums[back] <= nums[i] { deq.pop_back(); } else { break; }
  }

Trampa 2: Desalinear la Condición de Caducidad de la Ventana#

• El error: Escribir front <= i - k usando tipos con signo que pueden dar resultados negativos cuando i < k.
• Por qué falla: En Rust, los índices son usize. Si escribes i - k cuando i < k, se produce un pánico inmediato por overflow.
• La solución: Escribir la condición sumando k al frente:

  if front + k <= i {
      deq.pop_front();
  }

Esta suma es matemáticamente equivalente a front <= i - k y es 100% segura contra desbordamientos para cualquier i.

Trampa 3: Asumir que la Cola Guarda Valores en Lugar de Índices#

• El error: Intentar almacenar los números directos en el Deque (deq.push_back(nums[i])).
• Por qué falla: Si dos números iguales entran en distintos momentos de la ventana, al salir el primero no puedes saber si debes eliminarlo o si pertenece a la ocurrencia posterior que aún está dentro de la ventana.
• La solución: Guardar invariablemente los índices de posición en el Deque y consultar el valor con nums[deq.front()].

5. Implementación Canónica en Rust y Comparativa con Python#

Implementación en Rust (practica-rust/dia_51.rs)#

use std::collections::VecDeque;

/// LeetCode 239: Sliding Window Maximum con VecDeque en O(N) amortizado.
pub fn max_sliding_window(nums: &[i32], k: usize) -> Vec<i32> {
    if nums.is_empty() || k == 0 {
        return Vec::new();
    }
    let n = nums.len();
    if k == 1 {
        return nums.to_vec();
    }
    if k >= n {
        return vec![*nums.iter().max().unwrap()];
    }

    let mut deq: VecDeque<usize> = VecDeque::with_capacity(k);
    let mut result = Vec::with_capacity(n - k + 1);

    for i in 0..n {
        // 1. Desalojo por la izquierda de elementos caducados
        if let Some(&front) = deq.front() {
            if front + k <= i {
                deq.pop_front();
            }
        }

        // 2. Mantenimiento del orden monótono decreciente por la derecha
        while let Some(&back) = deq.back() {
            if nums[back] <= nums[i] {
                deq.pop_back();
            } else {
                break;
            }
        }

        // 3. Inserción del índice actual
        deq.push_back(i);

        // 4. Registrar el máximo si la ventana está completa
        if i + 1 >= k {
            result.push(nums[*deq.front().unwrap()]);
        }
    }

    result
}

/// Sliding Window Minimum con VecDeque monótonamente creciente.
pub fn min_sliding_window(nums: &[i32], k: usize) -> Vec<i32> {
    if nums.is_empty() || k == 0 {
        return Vec::new();
    }
    let n = nums.len();
    if k == 1 {
        return nums.to_vec();
    }
    if k >= n {
        return vec![*nums.iter().min().unwrap()];
    }

    let mut deq: VecDeque<usize> = VecDeque::with_capacity(k);
    let mut result = Vec::with_capacity(n - k + 1);

    for i in 0..n {
        if let Some(&front) = deq.front() {
            if front + k <= i {
                deq.pop_front();
            }
        }

        while let Some(&back) = deq.back() {
            if nums[back] >= nums[i] {
                deq.pop_back();
            } else {
                break;
            }
        }

        deq.push_back(i);

        if i + 1 >= k {
            result.push(nums[*deq.front().unwrap()]);
        }
    }

    result
}

Implementación de Referencia en Python (practica/dia_51_monotonic_deque_sliding_window.py)#

from collections import deque
from typing import List


def max_sliding_window(nums: List[int], k: int) -> List[int]:
    """LeetCode 239: Sliding Window Maximum en O(N) con deque."""
    if not nums or k <= 0:
        return []
    if k == 1:
        return list(nums)

    deq: deque[int] = deque()
    result: List[int] = []

    for i in range(len(nums)):
        # 1. Purgar elementos caducados
        if deq and deq[0] < i - k + 1:
            deq.popleft()

        # 2. Purgar menores por la derecha
        while deq and nums[deq[-1]] <= nums[i]:
            deq.pop()

        # 3. Insertar
        deq.append(i)

        # 4. Registrar máximo
        if i >= k - 1:
            result.append(nums[deq[0]])

    return result

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Ejercicios de Práctica Independiente y Casos Límite#

1. Paso Límite 1: Ventana de Tamaño k = 1: - Para cualquier arreglo nums, comprueba que max_sliding_window(&nums, 1) retorne exactamente una copia idéntica del arreglo de entrada.
2. Paso Límite 2: Ventana Mayor o Igual a la Longitud del Arreglo (k ≥ N): - Para nums = [1, 5, 2], con k = 5, verifica que retorne un único elemento [5].
3. Paso Límite 3: Arreglo Estrictamente Decreciente: - Para nums = [9, 8, 7, 6, 5], con k = 3, verifica que en cada paso la cola solo contenga un elemento tras otro porque cada nuevo número es menor, y que los máximos sean [9, 8, 7].

Navegación final:

• ← Sesión 50: Trapping Rain Water (CTCI 17.21): Two Pointers vs Monotonic Stack
• Sesión 52: Árbol Binario Indexado (Fenwick Tree / BIT) y Prefijos Dinámicos →
• Glosario Maestro
• Guía de Diagramas de Arquitectura