Pila de mínimo / Cola de mínimo

En este artículo consideramos tres problemas: primero modificaremos una pila de forma que nos permita encontrar el elemento más pequeño de la pila en $O(1)$ , después haremos lo mismo con una cola, y finalmente usaremos estas estructuras de datos para encontrar el mínimo en todos los subarreglos de longitud fija de un arreglo en $O(n)$

Modificación de la pila

Queremos modificar la estructura de datos pila de tal forma que sea posible encontrar el elemento más pequeño de la pila en tiempo $O(1)$ , manteniendo el mismo comportamiento asintótico al agregar y quitar elementos de la pila. Recordatorio rápido: en una pila solo agregamos y quitamos elementos por un extremo.

Para hacer esto, no solo guardaremos los elementos en la pila, sino que los guardaremos en pares: el elemento en sí y el mínimo en la pila desde este elemento hacia abajo.


stack<pair<int, int>> st;

Es claro que encontrar el mínimo en toda la pila consiste solo en mirar el valor stack.top().second.

También es obvio que agregar o quitar un elemento nuevo de la pila se puede hacer en tiempo constante.

Implementación:

Agregar un elemento:


int new_min = st.empty() ? new_elem : min(new_elem, st.top().second);
st.push({new_elem, new_min});

Quitar un elemento:


int removed_element = st.top().first;
st.pop();

Encontrar el mínimo:


int minimum = st.top().second;

Modificación de la cola (método 1)

Ahora queremos lograr las mismas operaciones con una cola, es decir, queremos agregar elementos al final y quitarlos del frente.

Aquí consideramos un método simple para modificar una cola. Tiene una gran desventaja, sin embargo, porque la cola modificada en realidad no guardará todos los elementos.

La idea clave es guardar en la cola solo los elementos que se necesitan para determinar el mínimo. Es decir, mantendremos la cola en orden no decreciente (el valor más pequeño estará en el frente), y por supuesto no de cualquier forma: el mínimo real tiene que estar siempre contenido en la cola. De esta forma el elemento más pequeño estará siempre en el frente de la cola. Antes de agregar un elemento nuevo a la cola, basta con hacer un “corte”: quitaremos todos los elementos del final de la cola que sean mayores que el elemento nuevo, y después agregaremos el elemento nuevo a la cola. De esta forma no rompemos el orden de la cola, y tampoco perderemos el elemento actual si en algún paso posterior es el mínimo. Todos los elementos que quitamos nunca pueden ser un mínimo por sí mismos, así que esta operación está permitida. Cuando queremos extraer un elemento del frente, en realidad podría no estar ahí (porque lo quitamos antes al agregar un elemento más pequeño). Por lo tanto, al borrar un elemento de una cola necesitamos conocer el valor del elemento. Si el frente de la cola tiene el mismo valor, podemos quitarlo de forma segura; si no, no hacemos nada.

Consideremos las implementaciones de las operaciones anteriores:


deque<int> q;

Encontrar el mínimo:


int minimum = q.front();

Agregar un elemento:


while (!q.empty() && q.back() > new_element)
    q.pop_back();
q.push_back(new_element);

Quitar un elemento:


if (!q.empty() && q.front() == remove_element)
    q.pop_front();

Es claro que en promedio todas estas operaciones solo toman tiempo $O(1)$ (porque cada elemento solo se puede insertar y extraer una vez).

Modificación de la cola (método 2)

Esta es una modificación del método 1. Queremos poder quitar elementos sin saber qué elemento hay que quitar. Podemos lograrlo guardando el índice de cada elemento en la cola. Y también recordamos cuántos elementos ya agregamos y quitamos.


deque<pair<int, int>> q;
int cnt_added = 0;
int cnt_removed = 0;

Encontrar el mínimo:


int minimum = q.front().first;

Agregar un elemento:


while (!q.empty() && q.back().first > new_element)
    q.pop_back();
q.push_back({new_element, cnt_added});
cnt_added++;

Quitar un elemento:


if (!q.empty() && q.front().second == cnt_removed) 
    q.pop_front();
cnt_removed++;

Modificación de la cola (método 3)

Aquí consideramos otra forma de modificar una cola para encontrar el mínimo en $O(1)$ . Esta forma es un poco más complicada de implementar, pero esta vez sí guardamos todos los elementos. Y también podemos quitar un elemento del frente sin conocer su valor.

La idea es reducir el problema al problema de las pilas, que ya resolvimos. Así que solo necesitamos aprender a simular una cola usando dos pilas.

Hacemos dos pilas, s1 y s2. Por supuesto estas pilas serán de la forma modificada, de modo que podamos encontrar el mínimo en $O(1)$ . Agregaremos elementos nuevos a la pila s1, y quitaremos elementos de la pila s2. Si en algún momento la pila s2 está vacía, movemos todos los elementos de s1 a s2 (lo que esencialmente invierte el orden de esos elementos). Finalmente, encontrar el mínimo en una cola consiste simplemente en encontrar el mínimo de ambas pilas.

Así realizamos todas las operaciones en $O(1)$ en promedio (cada elemento se agregará una vez a la pila s1, se transferirá una vez a s2, y se extraerá una vez de s2)

Implementación:


stack<pair<int, int>> s1, s2;

Encontrar el mínimo:


if (s1.empty() || s2.empty()) 
    minimum = s1.empty() ? s2.top().second : s1.top().second;
else
    minimum = min(s1.top().second, s2.top().second);

Agregar un elemento:


int minimum = s1.empty() ? new_element : min(new_element, s1.top().second);
s1.push({new_element, minimum});

Quitar un elemento:


if (s2.empty()) {
    while (!s1.empty()) {
        int element = s1.top().first;
        s1.pop();
        int minimum = s2.empty() ? element : min(element, s2.top().second);
        s2.push({element, minimum});
    }
}
int remove_element = s2.top().first;
s2.pop();

Encontrar el mínimo de todos los subarreglos de longitud fija

Supongamos que nos dan un arreglo $A$ de longitud $N$ y un $M \le N$ dado. Tenemos que encontrar el mínimo de cada subarreglo de longitud $M$ en este arreglo, es decir, tenemos que encontrar:

$\min_{0 \le i \le M-1} A[i], \min_{1 \le i \le M} A[i], \min_{2 \le i \le M+1} A[i],\dots, \min_{N-M \le i \le N-1} A[i]$

Tenemos que resolver este problema en tiempo lineal, es decir, $O(n)$ .

Podemos usar cualquiera de las tres colas modificadas para resolver el problema. Las soluciones deberían ser claras: agregamos los primeros $M$ elementos del arreglo, encontramos y mostramos su mínimo, después agregamos el siguiente elemento a la cola y quitamos el primer elemento del arreglo, encontramos y mostramos su mínimo, etc. Como todas las operaciones con la cola se realizan en tiempo constante en promedio, la complejidad de todo el algoritmo será $O(n)$ .