Sesión 66: Test Diagnóstico 3 — Consultas de Rango 2D y Colas Monótonas: Trapping Rain Water II y Sliding Window Maximum (LeetCode 407 & 239)#

Tiempo estimado: 75-85 minutos. Nivel: De Junior/Trainee a Staff Specialist. Herramientas obligatorias: Hoja cuadriculada, lápiz, regla y bolígrafos de dos colores.

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

Consulta rápida: Glosario Maestro | Guía de Diagramas

Trapping Rain Water 2D (Atrapamiento de Agua en 3D / Superficies)#

• (a) En palabras simples (intuición): Imagina una bandeja para hornear con bordes de metal y montañitas esculpidas en el fondo. Si llueve sobre la bandeja, el agua comenzará a acumularse en los huecos, pero en cuanto el nivel del agua alcance el borde más bajo de la bandeja, cualquier exceso de agua se derramará por ese borde hacia afuera. Para saber cuánta agua queda atrapada, debes vigilar constantemente el punto más bajo de todo el borde exterior.
• (b) Definición técnica paso a paso: Problema de modelado hidráulico sobre una matriz discreta M × N:
• Las celdas en el borde perimetral no pueden retener agua (su agua se derrama fuera de la cuadrícula).
• El volumen de agua en una celda interior (r, c) está limitado por la altura mínima del contorno cerrado que la rodea hasta el exterior.
• Se procesa mediante un algoritmo de contracción de contorno: se inserta el perímetro exterior en un Min-Heap, y en cada paso se extrae la celda con menor elevación, expandiendo el frente hacia las celdas vecinas no visitadas.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa con una cola de prioridad std::collections::BinaryHeap<Cell>. Como BinaryHeap en Rust es un Max-Heap por defecto, se invierte la implementación del trait Ord para que opere como un Min-Heap de bajo costo sin asignaciones dinámicas.
• (d) Error típico de Junior: Intentar calcular máximos independientes por fila y columna como en Trapping Rain Water 1D (LeetCode 42); en 2D el agua puede fugarse en diagonal o en zig-zag a través de cualquier punto bajo, requiriendo un enfoque topológico en grafos.

Monotonic Deque (Cola Doblemente Enlazada Monótona)#

• (a) En palabras simples (intuición): Imagina una fila de personas donde cada persona nueva que entra es más joven que las anteriores. Si llega un nuevo postulante y es tanto más fuerte como más joven que los que están al final de la fila, esos que estaban al final pierden toda posibilidad de ganar y son despedidos de inmediato. La fila siempre queda estrictamente ordenada de mayor a menor fuerza, por lo que el campeón absoluto siempre está en la cabeza de la fila.
• (b) Definición técnica paso a paso: Estructura de datos basada en una cola de doble extremo (Double-Ended Queue) donde los elementos almacenados satisfacen un orden monotónico estricto (no creciente o no decreciente):
• Soporta inserciones y eliminaciones por ambos extremos (push_back, pop_back, pop_front).
• Permite consultar el valor extremo (mínimo o máximo) de una ventana deslizante de longitud K en tiempo amortizado O(1) por elemento.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa utilizando std::collections::VecDeque<usize> en el Heap, almacenando los índices de los elementos en lugar de sus valores crudos para poder validar la expiración temporal de la ventana.
• (d) Error típico de Junior: Usar una Priority Queue (Heap) ordinaria para Sliding Window Maximum, lo que introduce un factor logarítmico O(N log K) y exige desalojo perezoso innecesario en vez del óptimo lineal O(N).

Amortización Lineal O(N)#

• (a) En palabras simples (intuición): Aunque en una iteración particular el bucle while interno pueda expulsar a 4 o 5 personas de golpe de la cola, cada persona solo puede ser expulsada una única vez en toda su vida. Si tienes N personas, a lo largo de todo el programa ocurrirán como máximo N inserciones y N expulsiones.
• (b) Definición técnica paso a paso: Demostración matemática por el método del potencial:
• Cada elemento del arreglo se inserta en el VecDeque exactamente una vez (N operaciones push_back).
• Cada elemento puede ser retirado por el frente (pop_front) a lo sumo una vez, o por el fondo (pop_back) a lo sumo una vez ($ \le N$ operaciones pop).
• Número total de operaciones sobre el deque: a lo sumo 2N = O(N).
• Costo promedio por paso: (O(N)) / (N) = O(1) amortizado.
• (c) Cómo funciona en Rust (memoria y tipos): VecDeque utiliza un buffer circular contiguo en el Heap con capacidad preasignada with_capacity(k), minimizando las reasignaciones de memoria.
• (d) Error típico de Junior: Analizar la complejidad como O(N · K) viendo dos bucles anidados (for y while), sin notar el invariante de salida única.

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

La Dinámica de Propagación del Agua en LeetCode 407#

Visualicemos una matriz 3 × 6:

[ 1 , 4 , 3 , 1 , 3 , 2 ]
[ 3 , 2 , 1 , 3 , 2 , 4 ]
[ 2 , 3 , 3 , 2 , 3 , 1 ]

1. Paso Inicial (Perímetro Exterior al Min-Heap): - Se insertan todas las celdas del perímetro (las 14 celdas exteriores). - Las celdas interiores iniciales no visitadas son: (1, 1) con altura 2, (1, 2) con altura 1, (1, 3) con altura 3, (1, 4) con altura 2.
2. Propagación del Contorno: - El Min-Heap extrae siempre la celda perimetral más baja disponible. - Supongamos que el contorno alcanza la celda interior (1, 2) (altura física 1) a través de una barrera circundante con altura de agua efectiva 3. - Dado que la celda física está a altura 1 y el agua circundante está a altura 3, la columna de agua retenida es:
   Agua = 3 - 1 = 2 unidades
   - La nueva altura que se propaga hacia los vecinos no visitados es max(3, 1) = 3. - Al finalizar el escaneo de todas las celdas interiores, el volumen acumulado total es exactamente 4 unidades.

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

Diagrama Arquitectónico de Contorno Hidráulico#

Consulta el diagrama vectorial:

flowchart TD
    BORDER["Insertar celdas del perímetro en Min-Heap<br/>visited[r][c] = true"] --> POP["Extraer celda (h, r, c) más baja del Heap"]
    POP --> NEI["Para cada vecino (nr, nc) no visitado"]
    NEI --> WATER["agua += max(0, h - height[nr][nc])"]
    WATER --> PUSH["min_heap.push(max(h, height[nr][nc]), nr, nc)<br/>visited[nr][nc] = true"]
    PUSH --> CHK{"¿Quedan celdas en Heap?"}
    CHK -->|Sí| POP
    CHK -->|No| FIN(["Retornar total_water"])

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

Sliding Window Maximum (nums = [1, 3, -1, -3, 5], k = 3):#

Stack:
  deque: VecDeque<usize> (almacena índices)
  result: Vec<i32>

PASO i=0 (val = 1):
  deque está vacío -> push_back(0)
  deque: [0] (nums[0]=1)

PASO i=1 (val = 3):
  nums[0] (1) <= 3 -> pop_back(0)
  push_back(1)
  deque: [1] (nums[1]=3)

PASO i=2 (val = -1) -> Ventana completa de tamaño 3 [1, 3, -1]:
  nums[1] (3) > -1 -> se conserva 1
  push_back(2)
  deque: [1, 2] (valores: 3, -1)
  Máximo de la ventana = nums[deque.front()] = nums[1] = 3.
  result: [3]

PASO i=3 (val = -3):
  ¿deque.front() (1) expiró? i - k + 1 = 3 - 3 + 1 = 1 (1 >= 1, sigue vivo).
  nums[2] (-1) > -3 -> push_back(3)
  deque: [1, 2, 3] (valores: 3, -1, -3)
  Máximo de la ventana = nums[1] = 3.
  result: [3, 3]

PASO i=4 (val = 5):
  ¿deque.front() (1) expiró? i - k + 1 = 4 - 3 + 1 = 2 (1 < 2 -> EXPIRÓ!).
  pop_front() elimina índice 1.
  deque queda: [2, 3].
  nums[3] (-3) <= 5 -> pop_back(3)
  nums[2] (-1) <= 5 -> pop_back(2)
  push_back(4)
  deque: [4] (nums[4]=5)
  Máximo de la ventana = nums[4] = 5.
  result: [3, 3, 5]

4. Implementación Canónica en Rust (Compilable con rustc --test)#

Archivo de referencia: practica-rust/dia_66.rs

use std::cmp::Ordering;
use std::collections::{BinaryHeap, VecDeque};

#[derive(Copy, Clone, Eq, PartialEq)]
struct Cell {
    height: i32,
    r: usize,
    c: usize,
}

impl Ord for Cell {
    fn cmp(&self, other: &Self) -> Ordering {
        // Invertimos el orden para Min-Heap
        other.height.cmp(&self.height)
    }
}

impl PartialOrd for Cell {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

/// LeetCode 407: Trapping Rain Water II en O(M * N log(M * N))
pub fn trap_rain_water_2d(height_map: Vec<Vec<i32>>) -> i32 {
    let rows = height_map.len();
    if rows < 3 {
        return 0;
    }
    let cols = height_map[0].len();
    if cols < 3 {
        return 0;
    }

    let mut visited = vec![vec![false; cols]; rows];
    let mut min_heap: BinaryHeap<Cell> = BinaryHeap::new();

    for r in 0..rows {
        for c in 0..cols {
            if r == 0 || r == rows - 1 || c == 0 || c == cols - 1 {
                min_heap.push(Cell { height: height_map[r][c], r, c });
                visited[r][c] = true;
            }
        }
    }

    let mut total_water = 0;
    let directions: [(isize, isize); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];

    while let Some(cell) = min_heap.pop() {
        for (dr, dc) in directions {
            let nr = cell.r as isize + dr;
            let nc = cell.c as isize + dc;

            if nr >= 0 && nr < rows as isize && nc >= 0 && nc < cols as isize {
                let nr = nr as usize;
                let nc = nc as usize;

                if !visited[nr][nc] {
                    visited[nr][nc] = true;
                    if height_map[nr][nc] < cell.height {
                        total_water += cell.height - height_map[nr][nc];
                    }
                    min_heap.push(Cell {
                        height: cell.height.max(height_map[nr][nc]),
                        r: nr,
                        c: nc,
                    });
                }
            }
        }
    }

    total_water
}

/// LeetCode 239: Sliding Window Maximum en O(N) lineal
pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let k = k as usize;
    if nums.is_empty() || k == 0 {
        return Vec::new();
    }
    if k == 1 {
        return nums;
    }

    let mut deque: VecDeque<usize> = VecDeque::with_capacity(k);
    let mut result: Vec<i32> = Vec::with_capacity(nums.len() - k + 1);

    for i in 0..nums.len() {
        if let Some(&front_idx) = deque.front() {
            if front_idx + k <= i {
                deque.pop_front();
            }
        }

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

        deque.push_back(i);

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

    result
}

Implementación de Referencia en Python Tipado#

import collections
import heapq
from typing import List


def trap_rain_water_2d_py(height_map: List[List[int]]) -> int:
    """LeetCode 407 con Min-Heap y BFS en O(M * N log(M * N))."""
    if not height_map or not height_map[0]:
        return 0
    m, n = len(height_map), len(height_map[0])
    visited = [[False] * n for _ in range(m)]
    heap = []

    for r in range(m):
        for c in range(n):
            if r in (0, m - 1) or c in (0, n - 1):
                heapq.heappush(heap, (height_map[r][c], r, c))
                visited[r][c] = True

    total_water = 0
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while heap:
        h, r, c = heapq.heappop(heap)
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
                visited[nr][nc] = True
                if height_map[nr][nc] < h:
                    total_water += h - height_map[nr][nc]
                heapq.heappush(heap, (max(h, height_map[nr][nc]), nr, nc))

    return total_water


def max_sliding_window_py(nums: List[int], k: int) -> List[int]:
    """LeetCode 239 con Deque Monótono en O(N) lineal."""
    q = collections.deque()
    res = []

    for i, num in enumerate(nums):
        if q and q[0] <= i - k:
            q.popleft()
        while q and nums[q[-1]] <= num:
            q.pop()
        q.append(i)
        if i >= k - 1:
            res.append(nums[q[0]])

    return res

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

6. Navegación#

• ← Sesión 65: Test Diagnóstico 2 — Tries Compuestos y DSU
• Sesión 67: Test Diagnóstico 4 — Sistemas Distribuidos y Probabilísticos →
• Mapa del Curso
• Glosario Maestro
• Guía de Diagramas de Arquitectura