Sesión 31: Refuerzo y Evaluación de Stacks, Queues & Monotonic Stack#

Navegación rápida:

• ← Sesión 30: Evaluación — Linked Lists In-Place y Heaps
• Sesión 32: Evaluación — Árboles Binarios y BST →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_31.rs

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

En esta sesión evaluamos el dominio de estructuras LIFO avanzadas capaces de filtrar información redundante en tiempo lineal amortizado y resolver gramáticas anidadas. Consulta el Glosario Maestro y la Guía de Diagramas.

Pila Monótona Creciente (Monotonic Increasing Stack)#

• (a) En palabras simples (intuición): Una escalera donde cada peldaño que colocas debe ser más alto que el anterior. Si llega un peldaño más bajo, estás obligado a demoler a martillazos todos los peldaños anteriores que sean más altos que el nuevo hasta que la escalera vuelva a subir siempre hacia adelante.
• (b) Definición técnica paso a paso: Pila cuyos elementos preservan un orden monótono no decreciente de sus valores asociados (A[stack[0]] ≤ A[stack[1]] ≤ …). Al procesar un elemento entrante x, se extraen (pop) iterativamente todos los elementos del tope que violen la condición (A[top] > x), antes de insertar x.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa como un vector plano contiguo Vec<usize> que almacena índices del slice original. Los accesos e inserciones al final (push/pop) operan en la línea de caché L1/L2 con cero fragmentación.
• (d) Error típico de Junior: Almacenar directamente los valores numéricos (heights[i]) en lugar de los índices i; al perder el índice, es imposible calcular el ancho (w) o la distancia física entre barras.

Barra Limitante y Viga Horizontal#

• (a) En palabras simples (intuición): Una viga de madera que empujas hacia los lados a la altura del techo de una casa. La viga se expande libremente hasta que choca contra una pared más baja que ella a la izquierda y contra otra pared más baja a la derecha. La altura de esa casa es la cota máxima para ese tramo de techo.
• (b) Definición técnica paso a paso: Para cualquier barra k en el histograma, su rectángulo maximal asociado es aquel donde la altura es exactamente hₖ y su ancho abarca el rango continuo [L+1..R-1], donde L es el primer índice a la izquierda con altura estrictamente menor (h_L < hₖ) y R es el primer índice a la derecha con altura estrictamente menor (h_R < hₖ).
• (c) Cómo funciona en Rust (memoria y tipos): La pila monótona garantiza que cuando k se extrae debido a la barra i, R = i de forma inmediata, y L pasa a ser el nuevo tope de la pila tras el pop.
• (d) Error típico de Junior: Calcular el ancho simplemente como i - k, ignorando que la barra podía extenderse mucho más hacia la izquierda sobre barras intermedias más altas que ya fueron retiradas de la pila.

Centinela Virtual de Cierre (Altura 0)#

• (a) En palabras simples (intuición): Un piso falso a nivel del suelo que colocas al final de la construcción para obligar a que todas las vigas pendientes caigan y se midan antes de cerrar la obra.
• (b) Definición técnica paso a paso: Elemento ficticio de altura cero procesado en el índice virtual N (heights.len()). Dado que cualquier altura real h ≥ 0, este centinela fuerza el vaciado completo de la pila monótona en un único bucle unificado, eliminando la necesidad de duplicar código de cálculo de áreas al finalizar el recorrido.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa iterando sobre el rango inclusivo 0..=n, asignando let curr_h = if i == n { 0 } else { heights[i] };.
• (d) Error típico de Junior: Olvidar vaciar la pila tras el bucle principal; si el histograma es estrictamente creciente ([1, 2, 3, 4]), el algoritmo retornaría 0 porque ninguna barra se extraería nunca.

Pilas Duales de Contexto Jerárquico (Dual Stacks)#

• (a) En palabras simples (intuición): Dos blocs de notas en tu escritorio. En uno anotas cuántas veces debes repetir una tarea (la pila de números) y en el otro anotas qué habías escrito antes de que te interrumpieran con un paréntesis (la pila de textos).
• (b) Definición técnica paso a paso: Arquitectura de dos pilas sincronizadas para interpretar gramáticas formales recursivas: count_stack (que preserva el factor de repetición k) y string_stack (que preserva el prefijo acumulado del ámbito superior al abrirse un corchete '[').
• (c) Cómo funciona en Rust (memoria y tipos): Vec<usize> para los multiplicadores y Vec<String> para las cadenas suspendidas en el Heap. Al procesar ']', se extrae el prefijo, se expande la subexpresión y se restaura el contexto.
• (d) Error típico de Junior: Asumir que los multiplicadores siempre tienen un solo dígito (char.to_digit), fallando en entradas como "100[leetcode]".

Análisis de Costo Amortizado de Pila#

• (a) En palabras simples (intuición): Comprar fichas de casino. Cada vez que entras a la ruleta compras 1 ficha. No importa si luego en una sola jugada el croupier retira 5 fichas de golpe: nunca se pueden retirar más fichas de las que compraste en total.
• (b) Definición técnica paso a paso: Demostración matemática donde el costo de una secuencia de N operaciones se distribuye globalmente. Aunque una iteración individual puede ejecutar un bucle interno while con múltiples extracciones, cada uno de los N elementos ingresa a la pila exactamente 1 vez y se extrae a lo sumo 1 vez. El número total acumulado de operaciones de pila está acotado por 2N, garantizando una cota temporal de O(N) estricto.
• (c) Cómo funciona en Rust (memoria y tipos): Garantiza que un vector prealocado con Vec::with_capacity(n) ejecute la rutina completa sin realocaciones intermedias en tiempo lineal.
• (d) Error típico de Junior: Ver un bucle while anidado dentro de un bucle for y concluir precipitadamente que la complejidad es O(N²).

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

La Matemática del Rectángulo Máximo (LC 84)#

Sea un histograma con barras de alturas no negativas H = [h₀, h₁, …, h_{n-1}]. Cualquier rectángulo contenido dentro del histograma debe tener su base apoyada en el suelo y su límite superior alineado con la altura de al menos una de las barras que abarca. Por tanto, el problema consiste en hallar:

donde wₖ es el ancho máximo sobre el cual la barra k puede extenderse sin topar con ninguna barra más baja que hₖ.

¿Cómo calcula la Pila Monótona wₖ en O(1) amortizado? Supongamos que mantenemos en la pila índices cuyas alturas son no-decrecientes:

1. Si leemos el índice actual i y encontramos que hᵢ < h_{stack.top()}, la barra en el tope de la pila (llamémosla k) no puede continuar extendiéndose hacia la derecha, porque la barra i es un obstáculo insalvable más bajo. Su frontera derecha es R = i.
2. Extraemos k con stack.pop().
3. ¿Cuál es su frontera izquierda L? - Dado que la pila era monótona no-decreciente, todas las barras intermedias entre el nuevo tope de la pila y k eran más altas que k (y por tanto ya fueron extraídas previamente). - El elemento que queda ahora en el tope de la pila (stack.top()) es la primera barra a la izquierda estrictamente menor que k. - Por consiguiente, la frontera izquierda de k es L = stack.top().
4. El ancho libre disponible para la barra k es:
   wₖ = (R - 1) - (L + 1) + 1 = R - L - 1 = i - stack.top() - 1
5. ¿Qué ocurre si tras hacer pop(), la pila queda totalmente vacía? - Significa que no existe ninguna barra a la izquierda que sea menor que k. La barra k es la menor de todo el prefijo desde el índice 0 hasta i-1. - Por tanto, el ancho abarca desde el índice 0 hasta i-1, es decir:
   wₖ = i

¡Esta fórmula elemental calcula el rectángulo maximal de cada barra en tiempo exacto O(1)!

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 31 y Memoria en Rust](../diagrams/sesiones/dia_31.svg)
• Código fuente del diagrama: Fuente Mermaid

Flujo de Monotonic Stack en Histograma#

flowchart TD
    BAR["Barra actual i con altura h[i] (o centinela h=0 en i=N)"] --> CHK{"¿Pila no vacía Y h[stack.top()] > h[i]?"}
    CHK -->|Sí (Violación monótona)| POP["idx = stack.pop()<br/>altura = h[idx]<br/>ancho = i si pila vacía sino i - stack.top() - 1<br/>max_area = max(max_area, altura * ancho)"]
    POP --> CHK
    CHK -->|No (Orden respetado)| PUSH["stack.push(i) si i < N"]
    PUSH --> NEXT["Avanzar al siguiente índice i + 1"]

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

Ejecución de largest_rectangle_area(&[2, 1, 5, 6, 2, 3]):

STACK                                            HEAP
+-------------------------------+               +--------------------------------------+
| Frame largest_rectangle_area  |               | stack: Vec<usize>                    |
|   n: 6                        |               | Capacidad: 6                         |
|   max_area: 10                |               | [ 1, 4 ]                             |
|   stack: Vec<usize> ----------+-------------->+--------------------------------------+
+-------------------------------+

Paso a Paso Relevante (Llegada al índice 4 con h[4]=2):
Pila antes de procesar i=4: [ 1 (h=1), 2 (h=5), 3 (h=6) ]

1. curr_h = h[4] = 2.
   Top es 3 (h=6). Como 6 > 2:
   - idx = stack.pop() -> 3 (h=6)
   - stack no vacía, nuevo top = 2.
   - ancho = 4 - 2 - 1 = 1.
   - área = 6 * 1 = 6. max_area = 6.

2. Pila: [ 1 (h=1), 2 (h=5) ].
   Top es 2 (h=5). Como 5 > 2:
   - idx = stack.pop() -> 2 (h=5)
   - stack no vacía, nuevo top = 1.
   - ancho = 4 - 1 - 1 = 2.
   - área = 5 * 2 = 10. ¡NUEVO MAX_AREA = 10!

3. Pila: [ 1 (h=1) ].
   Top es 1 (h=1). Como 1 <= 2, se detiene el while.
   - stack.push(4).
   - Pila resultante: [ 1 (h=1), 4 (h=2) ].

4. Las 3 Trampas Clásicas en Entrevistas#

1. La Trampa del IndexError con Pila Vacía: - Calcular siempre i - stack.last() - 1 sin verificar si stack.is_empty(). Si la pila quedó vacía tras el pop, intentar leer el último elemento causará un pánico o excepción en tiempo de ejecución. Debes usar if stack.is_empty() { i } else { i - stack.last().unwrap() - 1 }.
2. Ignorar el Centinela al Final: - Si no agregas la altura virtual 0 al final, barras crecientes quedarán atrapadas en la pila para siempre y nunca calcularán su área. El centinela 0 garantiza que toda barra sea evaluada.
3. Parseo Incorrecto de Dígitos en Decode String: - Acumular dígitos como cadenas y convertirlos tarde, o ignorar que números como "25[a]" requieren la acumulación matemática curr_k = curr_k * 10 + digit.

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

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

//! Día 31: Refuerzo y Evaluación de Stacks, Queues & Monotonic Stack en Rust.

/// LeetCode 84: Largest Rectangle in Histogram con Pila Monótona en O(N) tiempo y espacio.
pub fn largest_rectangle_area(heights: &[u32]) -> u64 {
    if heights.is_empty() {
        return 0;
    }

    let n = heights.len();
    let mut stack: Vec<usize> = Vec::with_capacity(n);
    let mut max_area: u64 = 0;

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

        while let Some(&top_idx) = stack.last() {
            if heights[top_idx] > curr_h {
                stack.pop();
                let h = heights[top_idx] as u64;
                let w = if stack.is_empty() {
                    i as u64
                } else {
                    (i - stack.last().unwrap() - 1) as u64
                };
                let area = h * w;
                if area > max_area {
                    max_area = area;
                }
            } else {
                break;
            }
        }

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

    max_area
}

/// LeetCode 394: Decode String con Pilas Duales en O(L) tiempo y O(D + L) espacio.
pub fn decode_string(s: &str) -> String {
    if s.is_empty() {
        return String::new();
    }

    let mut count_stack: Vec<usize> = Vec::new();
    let mut string_stack: Vec<String> = Vec::new();
    let mut curr_str = String::new();
    let mut curr_k: usize = 0;

    for c in s.chars() {
        if c.is_ascii_digit() {
            let digit = c.to_digit(10).unwrap() as usize;
            curr_k = curr_k * 10 + digit;
        } else if c == '[' {
            count_stack.push(if curr_k > 0 { curr_k } else { 1 });
            string_stack.push(curr_str);
            curr_k = 0;
            curr_str = String::new();
        } else if c == ']' {
            let k = count_stack.pop().unwrap_or(1);
            let mut prev_str = string_stack.pop().unwrap_or_default();
            for _ in 0..k {
                prev_str.push_str(&curr_str);
            }
            curr_str = prev_str;
        } else {
            curr_str.push(c);
        }
    }

    curr_str
}

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

from typing import List

def largest_rectangle_area(heights: List[int]) -> int:
    """LC 84: Pila Monótona Creciente en O(N) tiempo estricto y O(N) espacio."""
    if not heights:
        return 0

    stack: List[int] = []
    max_area = 0
    n = len(heights)

    for i in range(n + 1):
        curr_h = 0 if i == n else heights[i]

        while stack and (i == n or heights[stack[-1]] > curr_h):
            h = heights[stack.pop()]
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * w)

        stack.append(i)

    return max_area

def decode_string(s: str) -> str:
    """LC 394: Decodificación jerárquica con Pilas Duales en O(L) tiempo y espacio."""
    count_stack: List[int] = []
    string_stack: List[str] = []
    curr_str = ""
    curr_k = 0

    for char in s:
        if char.isdigit():
            curr_k = curr_k * 10 + int(char)
        elif char == "[":
            count_stack.append(curr_k)
            string_stack.append(curr_str)
            curr_k = 0
            curr_str = ""
        elif char == "]":
            k = count_stack.pop()
            prev_str = string_stack.pop()
            curr_str = prev_str + (curr_str * k)
        else:
            curr_str += char

    return curr_str

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

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

1. LeetCode 84 — Largest Rectangle in Histogram (Hard): - Resuelve el problema aplicando la pila monótona con el centinela virtual de altura 0.
2. LeetCode 394 — Decode String (Medium): - Aplica las pilas duales para decodificar expresiones anidadas.
3. LeetCode 85 — Maximal Rectangle (Hard): - Puente multidimensional: reduce la matriz 2D a M llamadas consecutivas de LC 84.
4. LeetCode 739 — Daily Temperatures (Medium): - Práctica complementaria de pila monótona decreciente para distancias temporales.

8. Tarea en Papel para Hoy#

Toma una hoja y realiza a mano la traza completa:

1. Dibuja el histograma [3, 1, 4, 2].
2. Escribe la tabla de variables (i, curr_h, stack, h, w, area, max_area) paso a paso incorporando el centinela virtual 0 en la posición 4.
3. Comprueba cuál es el rectángulo máximo y qué barras lo componen.

Navegación:

• ← Volver a Sesión 30: Evaluación — Linked Lists In-Place y Heaps
• Avanzar a Sesión 32: Evaluación — Árboles Binarios y BST →