Sesión 21: El Patrón Monotonic Stack (Pila Monótona) y Consolidación Global de la Semana 3#

Navegación rápida:

← Sesión 20: CTCI Ch3 — Animal Shelter
Sesión 22: Grokking Ch6 — Grafos, BFS y Route Between Nodes →
Glosario Maestro
Guía de Diagramas de Arquitectura
Tiempo estimado de estudio: 60-75 minutos.
Código fuente compilado y probado: practica-rust/dia_21.rs

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

Cerramos la Semana 3 dominando el patrón más potente y cotizado en entrevistas FAANG para problemas de proximidad y geometría unidimensional: la Pila Monótona. Consulta el Glosario Maestro y la Guía de Diagramas.

Pila Monótona Decreciente (Monotonic Decreasing Stack)#

(a) En palabras simples (intuición): Una escalera descendente donde cada escalón que pisas es obligatoriamente más bajo que el anterior. Si aparece un escalón más alto, destruye y aplana a todos los escalones más bajos que estaban antes que él.
(b) Definición técnica paso a paso: Pila cuyos elementos almacenados mantienen en todo momento un orden estrictamente decreciente desde el fondo hacia el tope:

S[0] > S[1] > S[2] > \dots > S[top]

Al procesar un nuevo valor $X$ , se desapilan todos los elementos menores que $X$ . Esto convierte a $X$ en el "Siguiente Elemento Mayor a la Derecha" (Next Greater Element) para cada uno de los elementos expulsados.

(c) Cómo funciona en Rust (memoria y tipos): Un Vec<usize> en el Heap que guarda índices de un slice &[i32]. La condición while let Some(&top_idx) = stack.last() evalúa si el valor actual supera al del tope sin desapilar prematuramente.
(d) Error típico de Junior: Usar una pila decreciente cuando el problema pide el "siguiente elemento menor" (requiere la variante creciente).

Pila Monótona Creciente (Monotonic Increasing Stack)#

(a) En palabras simples (intuición): Una colina donde cada paso sube a mayor altura. Si de pronto llegas a un barranco bajo, ese barranco expulsa a todos los picos altos que sobresalían antes.
(b) Definición técnica paso a paso: Pila cuyos elementos aumentan estrictamente del fondo hacia el tope:

S[0] < S[1] < S[2] < \dots < S[top]

Se utiliza para encontrar el "Siguiente Elemento Menor a la Derecha" (Next Smaller Element), base del cálculo del área máxima en histogramas (LeetCode 84).

(c) Cómo funciona en Rust (memoria y tipos): Desapila elementos mientras curr_val < heights[top_idx].
(d) Error típico de Junior: Olvidar que los elementos que quedan en la pila al terminar el arreglo también deben vaciarse con un valor centinela.

Almacenamiento de Índices vs Valores#

(a) En palabras simples (intuición): En una carrera, anotar el número de carril y nombre del corredor en lugar de solo su tiempo. Si anotas su carril, puedes calcular tanto su tiempo como la distancia que le sacó a los demás.
(b) Definición técnica paso a paso: Principio cardinal de diseño por el cual se apilan los índices de posición (usize) en el arreglo en lugar de los valores reales. Almacenar el índice otorga información dual en tiempo constante: permite acceder al valor original con arr[idx] y calcular la distancia espacial con curr_idx - prev_idx.
(c) Cómo funciona en Rust (memoria y tipos): La pila se tipa como Vec<usize>, compatible directamente con la indexación sin conversiones de tipo cast forzadas.
(d) Error típico de Junior: Apilar solo los valores numéricos i32; cuando el problema pide "cuántos días esperar", es matemáticamente imposible deducir la distancia sin conocer los índices.

Amortización de Desapilado ( $2N ⟹ O(N)$ )#

(a) En palabras simples (intuición): Aunque en un día particular la basura se acumule y el camión tarde 10 minutos vaciando todos los contenedores de golpe, cada bolsa de basura solo fue depositada una vez y recogida una vez en toda la semana.
(b) Definición técnica paso a paso: Propiedad por la cual, a pesar de que el algoritmo contiene un bucle while anidado dentro de un bucle for, cada elemento del arreglo entra a la pila exactamente una vez (push) y sale a lo sumo una vez (pop). El número total de operaciones de pila está acotado estrictamente por $2N$ , garantizando tiempo lineal $O(N)$ absoluto.
(c) Cómo funciona en Rust (memoria y tipos): Se ejecuta en registros de CPU y saltos condicionales mínimos con cero llamadas a re-asignación en el Heap si se usa Vec::with_capacity(n).
(d) Error típico de Junior: Asumir erróneamente que dos bucles anidados (for y while) siempre equivalen a $O(N²)$ .

Sondeo Circular Virtual ( $2N$ Pasos con Módulo $\pmod N$ )#

(a) En palabras simples (intuición): Un reloj de manecillas. Cuando pasa de las 12:00 no necesitas construir un segundo reloj nuevo; simplemente sigues contando 1:00, 2:00 dando una segunda vuelta sobre la misma esfera.
(b) Definición técnica paso a paso: Técnica algorítmica para procesar arreglos circulares sin duplicar memoria física. Se itera en un rango virtual de $[0, 2N - 1]$ y se proyecta a los índices reales mediante idx = i % n. Solo se insertan elementos en la pila durante la primera vuelta ( $i < N$ ).
(c) Cómo funciona en Rust (memoria y tipos): Evita reservar un nuevo Vec concatenado vec![nums.clone(), nums.clone()].concat(), ahorrando memoria en el Heap y tiempo de copia.
(d) Error típico de Junior: Duplicar el vector físicamente en memoria, consumiendo el doble de RAM innecesariamente.

Histograma y Rectángulo Máximo (LeetCode 84)#

(a) En palabras simples (intuición): Encontrar la valla publicitaria rectangular más grande que quepa dentro del perfil de varios edificios pegados uno al lado del otro.
(b) Definición técnica paso a paso: Problema geométrico que consiste en determinar el área del mayor rectángulo completamente contenido bajo una serie de barras contiguas de ancho 1 y alturas dadas. Se resuelve en $O(N)$ utilizando una pila monótona creciente para identificar los límites izquierdo y derecho de expansión de cada barra.
(c) Cómo funciona en Rust (memoria y tipos): Cada barra desapilada actúa como la altura limitante height, y el ancho se deduce entre el índice actual i y el nuevo tope de la pila.
(d) Error típico de Junior: Probar todas las combinaciones de pares de barras en fuerza bruta cuadrática $O(N²)$ , provocando Time Limit Exceeded.

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

El Colapso de la Fuerza Bruta Cuadrática#

Consideremos el problema de Daily Temperatures (LeetCode 739): para cada día, queremos saber cuántos días debemos esperar para encontrar una temperatura más cálida. El algoritmo novato emplea dos bucles anidados:

PYTHON

# Fuerza bruta: O(N^2)
for i in range(len(temps)):
    for j in range(i + 1, len(temps)):
        if temps[j] > temps[i]:
            ans[i] = j - i
            break

Si $N = 100,000$ (típico en pruebas técnicas de LeetCode):

Operaciones en el peor caso \approx (N(N - 1)) / (2) = (10⁵ \times 10⁵) / (2) = 5 \times 10⁹ operaciones

Una CPU moderna ejecuta aproximadamente $10⁸$ operaciones por segundo.
Tiempo estimado de ejecución: 50 segundos $⟹$ ¡Time Limit Exceeded (TLE)!

La Intuición Física de la Línea de Visión (Skyline)#

Imaginemos una fila de personas observando hacia el horizonte derecho:

TEXT

Posiciones:     0     1     2     3     4     5     6
Temperaturas: [ 75 ,  71 ,  69 ,  72 ,  76 ]

El día 0 (temp 75) mira hacia la derecha.
Los días 1 (71) y 2 (69) son más fríos que 75. No resuelven el día 0, así que los guardamos en la pila: stack = [0, 1, 2] (temperaturas: [75, 71, 69]).
Llega el día 3 con temperatura 72: - Comparamos 72 con el tope (día 2, temp 69): ¡72 es mayor que 69! - El día 3 es la primera temperatura mayor que ve el día 2. - Calculamos su distancia: $3 - 2 = 1$ día. Desapilamos el día 2. - Siguiente tope (día 1, temp 71): ¡72 también es mayor que 71! - Distancia: $3 - 1 = 2$ días. Desapilamos el día 1. - Siguiente tope (día 0, temp 75): 72 no supera a 75. El desapilado se detiene. - Apilamos el día 3. Pila queda: [0, 3] (temperaturas: [75, 72]).
Llega el día 4 con temperatura 76: - 76 supera a 72 $\to$ resuelve el día 3 ( $4 - 3 = 1$ ). - 76 supera a 75 $\to$ resuelve el día 0 ( $4 - 0 = 4$ ).

¡Cada elemento fue evaluado y resuelto en el momento exacto en que apareció su destructor!

Demostración Formal del Costo Lineal $O(N)$ #

Analicemos la cantidad total de operaciones de pila realizadas en todo el programa:

Cada índice $i \in [0, N - 1]$ se inserta en la pila exactamente una sola vez:

Total de llamadas a push() = N

Un elemento solo puede ser desapilado si previamente fue apilado. Ningún elemento puede desapilarse dos veces:

Total de llamadas a pop() \leq N

Suma acumulada de operaciones:

Operaciones Totales \leq Total de push + Total de pop \leq N + N = 2N

Dividiendo por el número de elementos $N$ :

Complejidad Temporal Final = O(2N) = O(N) tiempo lineal estricto.

3. Visualización Paso a Paso y Gráfica de Memoria en Rust#

Diagramas de Arquitectura#

Gráfico SVG vectorial: ![Visualización del Día 21 y Memoria en Rust](../diagrams/sesiones/dia_21.svg)
Código fuente del diagrama: Fuente Mermaid

Flujo de Expulsión en Pila Monótona Decreciente#

DIAGRAMA MERMAID

flowchart TD
    A["Elemento actual: curr_val en índice i"] --> B{"¿Pila no vacía y curr_val > arr[top_idx]?"}
    B -- Sí --> C["prev_idx = stack.pop()"]
    C --> D["ans[prev_idx] = i - prev_idx"]
    D --> B
    B -- No --> E["stack.push(i)"]
    E --> F["Avanzar al siguiente índice i + 1"]

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

Ejecución de daily_temperatures(&[73, 74, 75, 71, 69, 72]):

TEXT

STACK                                            HEAP
+-------------------------------+               +--------------------------------------+
| Frame daily_temperatures      |               | ans: Vec<usize> (len: 6)             |
|   n: 6                        |               | [ 0, 0, 0, 0, 0, 0 ]                 |
|   ans: Vec<usize> ------------+-------------->+--------------------------------------+
|   stack: Vec<usize> ----------+------+        +--------------------------------------+
|   curr_idx: 0                 |      +------->| stack: Vec<usize> (cap: 6)           |
+-------------------------------+               | [ ]                                  |
                                                +--------------------------------------+

Paso 0: curr_idx = 0 (val = 73). Pila vacía -> stack.push(0). Stack: [ 0 ]
Paso 1: curr_idx = 1 (val = 74). 74 > arr[0] (73) -> pop(0).
        ans[0] = 1 - 0 = 1.
        stack.push(1). Stack: [ 1 ]
Paso 2: curr_idx = 2 (val = 75). 75 > arr[1] (74) -> pop(1).
        ans[1] = 2 - 1 = 1.
        stack.push(2). Stack: [ 2 ]
Paso 3: curr_idx = 3 (val = 71). 71 < arr[2] (75) -> stack.push(3). Stack: [ 2, 3 ]
Paso 4: curr_idx = 4 (val = 69). 69 < arr[3] (71) -> stack.push(4). Stack: [ 2, 3, 4 ]
Paso 5: curr_idx = 5 (val = 72).
        72 > arr[4] (69) -> pop(4): ans[4] = 5 - 4 = 1.
        72 > arr[3] (71) -> pop(3): ans[3] = 5 - 3 = 2.
        72 < arr[2] (75) -> se detiene.
        stack.push(5). Stack: [ 2, 5 ]

Resultado en Heap:
ans: [ 1, 1, 0, 2, 1, 0 ]
Los índices 2 y 5 quedaron en la pila; sus celdas en ans conservan el 0 inicial por defecto.

4. Implementación Canónica en Rust + Comparativa con Python#

Implementación Canónica en Rust (`practica-rust/dia_21.rs`)#

RUST

//! Día 21: Patrón Monotonic Stack y Consolidación Semana 3 en Rust.
//! Compilable y verificable con `rustc --test`.

/// LeetCode 739: Daily Temperatures con Pila Monótona Decreciente en O(N).
pub fn daily_temperatures(temperatures: &[i32]) -> Vec<usize> {
    let n = temperatures.len();
    let mut ans = vec![0; n];
    let mut stack: Vec<usize> = Vec::with_capacity(n);

    for curr_idx in 0..n {
        let curr_val = temperatures[curr_idx];
        while let Some(&top_idx) = stack.last() {
            if curr_val > temperatures[top_idx] {
                let prev_idx = stack.pop().unwrap();
                ans[prev_idx] = curr_idx - prev_idx;
            } else {
                break;
            }
        }
        stack.push(curr_idx);
    }

    ans
}

/// LeetCode 503: Next Greater Element II en arreglo circular en O(N).
pub fn next_greater_elements_circular(nums: &[i32]) -> Vec<i32> {
    let n = nums.len();
    if n == 0 { return Vec::new(); }

    let mut res = vec![-1; n];
    let mut stack: Vec<usize> = Vec::new();

    for i in 0..(2 * n) {
        let idx = i % n;
        let val = nums[idx];

        while let Some(&top_idx) = stack.last() {
            if val > nums[top_idx] {
                let prev_idx = stack.pop().unwrap();
                res[prev_idx] = val;
            } else {
                break;
            }
        }

        if i < n {
            stack.push(idx);
        }
    }

    res
}

/// LeetCode 84: Largest Rectangle in Histogram con Pila Monótona Creciente en O(N).
pub fn largest_rectangle_area(heights: &[i32]) -> i32 {
    let n = heights.len();
    let mut stack: Vec<usize> = Vec::with_capacity(n);
    let mut max_area = 0;

    for i in 0..=n {
        let curr_height = if i == n { 0 } else { heights[i] };

        while let Some(&top_idx) = stack.last() {
            if curr_height < heights[top_idx] {
                let h_idx = stack.pop().unwrap();
                let height = heights[h_idx];
                let width = match stack.last() {
                    Some(&prev_idx) => (i - prev_idx - 1) as i32,
                    None => i as i32,
                };
                max_area = max_area.max(height * width);
            } else {
                break;
            }
        }

        stack.push(i);
    }

    max_area
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_daily_temperatures() {
        let temps = [73, 74, 75, 71, 69, 72, 76, 73];
        assert_eq!(daily_temperatures(&temps), vec![1, 1, 4, 2, 1, 1, 0, 0]);
    }

    #[test]
    fn test_circular_next_greater() {
        let nums = [1, 2, 1];
        assert_eq!(next_greater_elements_circular(&nums), vec![2, -1, 2]);
    }

    #[test]
    fn test_largest_rectangle() {
        let heights = [2, 1, 5, 6, 2, 3];
        assert_eq!(largest_rectangle_area(&heights), 10);
    }
}

Implementación Canónica en Python (`practica/dia_21_monotonic_stack.py`)#

PYTHON

from typing import List

def daily_temperatures(temperatures: List[int]) -> List[int]:
    """LeetCode 739: Monotonic Decreasing Stack de índices en O(N)."""
    n = len(temperatures)
    ans = [0] * n
    stack: List[int] = []

    for curr_idx, curr_val in enumerate(temperatures):
        while stack and curr_val > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            ans[prev_idx] = curr_idx - prev_idx
        stack.append(curr_idx)

    return ans

def next_greater_element_circular(nums: List[int]) -> List[int]:
    """LeetCode 503: Next Greater Element en arreglo circular con 2N pasadas."""
    n = len(nums)
    res = [-1] * n
    stack: List[int] = []

    for i in range(2 * n):
        idx = i % n
        while stack and nums[idx] > nums[stack[-1]]:
            prev_idx = stack.pop()
            res[prev_idx] = nums[idx]
        if i < n:
            stack.append(idx)

    return res

5. Las 3 Trampas Clásicas en Entrevistas#

Guardar Valores en Lugar de Índices: - Si guardas temperatures[i] en el stack en lugar de i, podrás saber cuál es el valor mayor, pero serás incapaz de calcular la distancia temporal (curr_idx - prev_idx). Guarda siempre los índices.
Confundir la Orientación de la Monotonicidad: - Para buscar el siguiente elemento mayor, necesitas una pila decreciente (porque los valores grandes desalojan a los pequeños). Para buscar el siguiente elemento menor, necesitas una pila creciente.
Arreglos Circulares con Duplicación Física de Memoria: - En LeetCode 503, duplicar físicamente el arreglo (nums + nums) gasta $O(N)$ memoria extra y requiere re-asignar un bloque contiguo en Heap. Itera siempre con un índice virtual $2N$ y operador módulo i % n.

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

Pregunta 1: ¿Por qué una pila monótona tiene una complejidad asintótica de O(N) si claramente contiene un bucle while anidado dentro de un bucle for?

Respuesta Técnica Detallada: La regla heurística de que "dos bucles anidados implican $O(N²)$ " solo es válida cuando el bucle interno realiza hasta $N$ iteraciones en cada una de las iteraciones del bucle externo de forma independiente. En una pila monótona, el bucle while ejecuta exclusivamente la operación stack.pop(). Para que un elemento sea desapilado por el while, previamente tuvo que haber sido apilado por la instrucción stack.push() del bucle for. Dado que el bucle for se ejecuta exactamente $N$ veces, se ejecutan como máximo $N$ operaciones push(). Por consiguiente, el bucle while no puede ejecutarse más de $N$ veces en total a lo largo de toda la vida del programa, sin importar cómo se distribuyan los desapilados entre las diferentes iteraciones. La suma acumulada de operaciones del bucle interno no supera $N$ , demostrando formalmente un costo lineal amortizado $O(N)$ .

Pregunta 2: En el problema del histograma (LeetCode 84), ¿por qué es necesario agregar un centinela de altura cero (height = 0) al final del recorrido?

Respuesta Técnica Detallada: Si el histograma contiene barras que terminan en orden estrictamente creciente (ejemplo: [1, 2, 3, 4, 5]): En cada iteración $i$ , la barra actual es mayor que la anterior, por lo que nunca se activa la condición de desapilado curr_height < heights[top_idx]. Todas las barras se quedan almacenadas dentro de la pila sin haber calculado sus áreas. Al agregar virtualmente una barra final en el índice $N$ con altura $0$ (el centinela): Como toda altura válida de histograma es $\geq 1$ (o $\geq 0$ ), la altura $0$ es forzosamente menor o igual que cualquier barra residual presente en la pila. Esto fuerza a la pila a desapilar absolutamente todos los elementos restantes, garantizando que el cálculo de áreas se complete para cada barra sin requerir código duplicado de vaciado tras el bucle.

Pregunta 3: ¿Cómo se deduce matemáticamente la fórmula del ancho width = i - prev_idx - 1 en el algoritmo del rectángulo máximo de histograma?

Respuesta Técnica Detallada: Cuando desapilamos una barra de índice h_idx con altura H:

El índice actual i representa el primer límite derecho donde una barra es estrictamente menor que H (el borde derecho del rectángulo).
El nuevo elemento que queda en el tope de la pila tras el pop (prev_idx = stack.last()) representa el primer límite izquierdo donde una barra es estrictamente menor que H (el borde izquierdo).
Todas las barras intermedias situadas estrictamente entre prev_idx y i tienen alturas mayores o iguales a H.
La cantidad de barras continuas comprendidas en el intervalo abierto $(prevᵢdx, i)$ es: $Ancho = (i - 1) - (prevᵢdx + 1) + 1 = i - prevᵢdx - 1$
Si la pila queda vacía (stack.last() == None), significa que no existe ninguna barra menor a la izquierda; por tanto, el rectángulo se extiende desde el inicio del arreglo ($0$) hasta $i$ , teniendo un ancho exacto de $i$ .

Pregunta 4: ¿Cuál es la diferencia algorítmica entre buscar el "Siguiente Mayor a la Derecha" frente al "Anterior Mayor a la Izquierda"?

Respuesta Técnica Detallada: Ambos problemas se resuelven con el patrón de Pila Monótona, pero varían en la dirección del recorrido o en el rol del elemento consultado:

Siguiente Mayor a la Derecha (Next Greater Right):
Recorrido de izquierda a derecha ( $0 \to N - 1$ ).
La respuesta para el elemento desapilado prev_idx es el elemento actual visitante curr_val que provocó su expulsión.
Anterior Mayor a la Izquierda (Previous Greater Left):
Recorrido de izquierda a derecha ( $0 \to N - 1$ ).
La respuesta para el elemento actual visitante curr_idx es el elemento que queda como tope en la pila después de haber expulsado a todos los elementos menores que él.

Ambas consultas se resuelven en $O(N)$ tiempo lineal.

Pregunta 5: En Rust, ¿por qué es preferible inicializar el vector de respuestas con vec![0; n] o vec![-1; n] en lugar de usar Vec::new() y empujar con push()?

Respuesta Técnica Detallada: Por acceso aleatorio indexado y localidad de memoria: En el algoritmo de Pila Monótona, las respuestas no se resuelven en orden secuencial $0, 1, 2, \dots$ : Un día en la posición $5$ puede resolver simultáneamente a los días anteriores en las posiciones $4, 3, 1$ . Para asignar la respuesta en ans[prev_idx] = distance: El vector ans debe tener su memoria completamente pre-asignada e indexable en el rango $[0, n - 1]$ . Si usáramos un vector vacío, intentar hacer ans[4] = 1 provocaría un pánico inmediato por acceso fuera de límites (index out of bounds). Además, vec![0; n] realiza una única asignación contigua en el Heap mediante alloc_zeroed, evitando realocaciones y copias en caliente.

7. Puente a LeetCode y Práctica de Código#

LeetCode 739 — Daily Temperatures (Medium): - Pila monótona decreciente de distancias temporal $O(N)$ .
LeetCode 496 — Next Greater Element I (Easy): - Monotonic Stack + HashMap para consultas de subconjuntos.
LeetCode 503 — Next Greater Element II (Medium): - Pila monótona con recorrido circular virtual $2N$ .
LeetCode 84 — Largest Rectangle in Histogram (Hard): - Aplicación maestra de Pila Monótona Creciente para cálculo de áreas en $O(N)$ .

8. Tarea en Papel para Hoy#

Toma una hoja de papel y realiza a mano la traza completa de largest_rectangle_area para: heights = [2, 1, 5, 6, 2, 3]

Dibuja el histograma con sus barras verticales.
Traza paso a paso la pila de índices y muestra cómo al llegar la barra de altura 2 (índice 4), se expulsan las barras 6 (índice 3) y 5 (índice 2).
Calcula el área del rectángulo formado por las barras de altura 5 y 6: $altura = 5, ancho = 2 ⟹ Área = 10$ .
Confirma que 10 es el área máxima global.

Navegación:

← Volver a Sesión 20: CTCI Ch3 — Animal Shelter
Avanzar a Sesión 22: Grokking Ch6 — Grafos, BFS y Route Between Nodes →