• deque
• set y multiset

[Sacar cosas de acá, y llevarlas a su propio artículo separado de ventana deslizante, que acá queda linkeado]

Una ventana deslizante (en inglés, Sliding Window) es un concepto que se utiliza mucho en el desarrollo de algoritmos. Consiste en un cierto intervalo, delimitado por dos índices $A$ y $B$, de forma tal que el intervalo incluye todos los $x$ tales que $A \leq x < B$, es decir, nuestro intervalo es de la forma $[A,B)$¹⁾.

Además, como sugiere su nombre, una característica esencial de las ventanas deslizantes es que sus extremos se van moviendo o “deslizando”, pero siempre en la misma dirección. Es decir, podemos comenzar por ejemplo con $A=B=0$, e incrementar cualquiera de ellos, a elección, en cada paso, pero nunca decrementarlos. Estos dos índices o punteros siempre avanzan: cuando se incrementa $A$, la ventana pierde un elemento por la izquierda, y cuando se incrementa $B$, la ventana gana un elemento por la derecha.

Sobre todo en inglés y en sitios de programación competitiva, a veces se le llama a las técnicas de ventanas deslizantes “two-pointers”, en referencia a las variables $A$ y $B$ que se mueven y apuntan siempre a los bordes de la ventana.

Es muy común trabajar con datos almacenados en un cierto arreglo, de manera tal que la ventana deslizante se refiere a un cierto subarreglo del mismo en cada momento, y querer mantener cierta información sobre los datos en la ventana deslizante en todo momento. Por ejemplo, una de las cosas más fáciles de mantener es la suma de sus elementos: para esto basta con tener una variable sumaTotal, inicialmente en 0, y actualizarla ante cada movimiento: cuando se agrega un elemento, se suma su valor a sumaTotal, y cuando se pierde un elemento, se resta su valor a sumaTotal, pudiendo así mover la ventana deslizante en $O(1)$ manteniendo su suma.

El problema que trataremos en esta sección es el de mantener el mínimo²⁾ de la ventana deslizante. El enfoque de utilizar una simple variable ya no sirve, porque no podemos “restar” en este caso, así que no tenemos manera de manejar eficientemente (sin recalcular desde 0) el caso en que se saca un elemento.

Supondremos que al comenzar tenemos $A=B=0$, y tendremos que programar 3 operaciones:

    void avanzarA();
    void avanzarB();
    int  minimoEnVentana();

Por ejemplo, si tenemos el siguiente arreglo:

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & 2 & 1 & 4 & 3 & 10 & 0\\ \hline \end{array}$$

Y ejecutamos la siguiente secuencia de movimientos de la ventana:

    avanzarB();
    avanzarA();
    avanzarB();
    avanzarB();
    avanzarB();
    avanzarB();
    avanzarB();
    avanzarA();
    avanzarA();
    avanzarB();

La ventana se movería de la siguiente manera:

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & 2 & 1 & 4 & 3 & 10 & 0\\ \hline A=B=0 & & & & & & \\ \end{array} \mbox{, ventana vacía}$$

avanzarB();

$$\begin{array}{|c|c|c|c|c|c|c|} \hline \color{red}2 & 2 & 1 & 4 & 3 & 10 & 0\\ \hline A=0 & B=1 & & & & & \\ \end{array} \mbox{, mínimo=$2$}$$

avanzarA();

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & 2 & 1 & 4 & 3 & 10 & 0\\ \hline & A=B=1 & & & & & \\ \end{array} \mbox{, ventana vacía}$$

avanzarB();

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red} 2 & 1 & 4 & 3 & 10 & 0\\ \hline & A=1 & B=2 & & & & \\ \end{array} \mbox{, mínimo=$2$}$$

avanzarB();

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{red} 1 & 4 & 3 & 10 & 0\\ \hline & A=1 & & B=3 & & & \\ \end{array} \mbox{, mínimo=$\color{red}1$}$$

avanzarB();

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{red} 1 & \color{red} 4 & 3 & 10 & 0\\ \hline & A=1 & & & B=4 & & \\ \end{array} \mbox{, mínimo=$1$}$$

avanzarB();

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{red} 1 & \color{red}4 & \color{red}3 & 10 & 0\\ \hline & A=1 & & & & B=5 & \\ \end{array} \mbox{, mínimo=$1$}$$

avanzarB();

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{red} 1 & \color{red}4 & \color{red}3 & \color{red}{10} & 0\\ \hline & A=1 & & & & & B=5 \\ \end{array} \mbox{, mínimo=$1$}$$

avanzarA();

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & 2 & \color{red} 1 & \color{red}4 & \color{red}3 & \color{red}{10} & 0\\ \hline & & A=2 & & & & B=5 \\ \end{array} \mbox{, mínimo=$1$}$$

avanzarA();

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & 2 & 1 & \color{red}4 & \color{red}3 & \color{red}{10} & 0\\ \hline & & & A=3 & & & B=5 \\ \end{array} \mbox{, mínimo=$\color{red}3$}$$

avanzarB();

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & 2 & 1 & \color{red}4 & \color{red}3 & \color{red}{10} & \color{red}0 & \\ \hline & & & A=3 & & & & B=6 \\ \end{array} \mbox{, mínimo=$\color{red}0$}$$

Llamaremos v al arreglo de números en cuestión: v=[2,2,1,4,3,10,0].

La forma más directa posible de implementar estas operaciones es calculando el mínimo desde cero cada vez:

void avanzarA() { A++; }
void avanzarB() { B++; }
int  minimoEnVentana()
{
    int mini = INF;
    for (int i = A; i < B; i++)
        mini = min(mini, v[i]);
    return mini;
}

En esta implementación, los avanzar son $O(1)$, pero obtener el mínimo es caro: cada operación tiene un costo $O(N)$.

Utilizando la estructura multiset³⁾, podremos mejorar muchísimo el enfoque anterior. La idea es mantener en todo momento un multiset con todos los elementos de la ventana. Podemos declararlo por ejemplo con:

    multiset<int> elementosEnVentana;

La idea es que en todo momento, el multiset tenga todos los elementos de la ventana actual. De esta forma, cuando se avanza $A$ será necesario borrar ese elemento del multiset, y cuando se avance $B$ será necesario agregar un nuevo elemento al multiset.

Al igual que set, multiset guarda sus elementos ordenados internamente, lo que nos permite acceder al mínimo con *elementosEnVentana.begin()⁴⁾. El código quedaría entonces:

void avanzarA()
{
    // Si hacemos simplemente elementosEnVentana.erase(v[A]) se borran TODAS las apariciones
    // de ese valor, pero queremos borrar una sola.
    elementosEnVentana.erase(elementosEnVentana.find(v[A]));
    A++; 
}
void avanzarB()
{
    elementosEnVentana.insert(v[B]);
    B++; 
}
int  minimoEnVentana()
{
    if (A == B)
        return INF; // VENTANA VACIA!!!
    else
        return *elementosEnVentana.begin();
}

Las tres operaciones tienen complejidad $O(\lg N)$, pues realizan $O(1)$ operaciones del multiset que tienen todas complejidad $O(\lg N)$.

Se puede realizar otra implementación de la misma complejidad asintótica, pero más eficiente en los factores constantes, utilizando priority_queue de la STL en lugar de multiset. Como no se pueden remover elementos arbitrarios de dicha estructura, habría que alterar un poco el código de minimoEnVentana, para que vaya sacando elementos hasta encontrar un valor que siga en la ventana, pero la idea central sería la misma.

Veremos ahora una implementación muy elegante, que utiliza estructuras de datos mucho más sencillas (ya que si bien ya vienen programadas, set y multiset son en sí estructuras mucho más complejas que vector o deque), y que realiza las 3 operaciones que queremos en $O(1)$.

Para esto, utilizaremos la idea de identificar “elementos dominados”, que es una idea muy útil en muchos problemas y no solo en este.

Supongamos que tenemos una situación como la del paso $A=1, B=5$ del ejemplo anterior:

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{red} 1 & \color{red}4 & \color{red}3 & 10 & 0\\ \hline & A=1 & & & & B=5 & \\ \end{array} \mbox{, mínimo=$1$}$$

En este caso, los elementos de nuestra ventana resultan ser [2,1,4,3], en ese orden. La pregunta que podemos hacernos, dada la situación actual, es la siguiente: ¿Cuáles de estos elementos tienen oportunidad de convertirse en el mínimo de la ventana en algún momento? Nuestro objetivo final es calcular el mínimo de la ventana en todo momento, pero si de alguna manera podemos asegurar que un elemento ya no podrá ser el mínimo jamás, podemos ignorarlo completamente, ya que ese elemento no nos interesa.

Si analizamos esta ventana [2,1,4,3] con cuidado, podemos concluir que los únicos elementos importantes son 1 y 3: los elementos 2 y 4 de esta ventana ya nunca podrán ser el mínimo de la ventana.

¿Por qué esto es así? Por un lado, el mínimo es actualmente 1, que es menor que 2. Eso hace que, hasta que ese 1 no se vaya de la ventana, 2 no tenga ninguna oportunidad de convertirse en el mínimo. Pero ese 1 está a la derecha del 2: por lo tanto, como todos los elementos se van sacando de la ventana siempre por el lado izquierdo, resulta que el 2 se va de la ventana antes que el 1. Resumiendo: desde ahora hasta que el 2 se vaya de la ventana, el 1, que es mejor, siempre estará presente en la ventana, y por lo tanto lo domina completamente. No es necesario en absoluto considerar ese 2, porque siempre será mejor opción el 1.

Esto ocurrió porque tenemos en la ventana un número 1, que es menor o igual que el número 2, y está a su derecha. Siempre que tengamos un número menor o igual a nuestra derecha, “no somos un número importante”, puesto que el otro es “al menos tan bueno como nosotros”, pero “nosotros nos vamos antes”.

La observación del párrafo anterior nos lleva a definir un elemento como dominado, cuando tiene otro a su derecha que es menor o igual. La idea es la que comentamos antes: Un elemento dominado tiene otro que es siempre mejor opción, así que se puede ignorar en favor del otro que lo domina. A los elementos que no son dominados por ningún otro, para ponerles algún nombre, los llamaremos los elementos dominantes.

La idea será guardar únicamente los elementos dominantes de la ventana, es decir, aquellos que no tengan a su derecha ningún elemento menor o igual. En nuestra ventana de ejemplo, los elementos dominantes son el 1 y el 3. Observemos que el elemento de la derecha de todo de la ventana siempre es dominante: Ya que no tiene ningún elemento a su derecha, y por lo tanto nadie puede dominarlo. Esto es lógico, ya que si a partir de ahora hiciéramos todo avanzarA, quedaría ese elemento solo, y se llegaría a convertir en el mínimo, que es algo que no debería nunca pasarle a un dominado.

Por ejemplo, si la ventana contuviera en algún momento los valores [3,4,2,3,4,7,5,10,11,9], podemos encontrar los siguientes dominados:

• El primer 3 es dominado por el 2
• El primer 4 es dominado por el 2
• El 7 es dominado por el 5
• El 10 y el 11 son dominados por el 9

Al dejar solo los dominantes, nos quedarían (en orden) los elementos [2,3,4,5,9]. ¿Tiene algo de especial esta lista? Sí: todos sus elementos se encuentran en orden estrictamente creciente.

Esta es una de las cosas buenas que tiene la eliminación de dominados: generalmente, cuando nos quedamos solamente con los elementos dominantes, ese conjunto resultante tendrá cierto orden o propiedad particular. En este problema, lo que ocurre es que los elementos dominantes tienen que estar sí o sí en orden creciente estricto: Si $x$ estuviera antes que $y$, pero $x \geq y$, entonces $y$ dominaría a $x$, y no podrían ser ambos dominantes. Si $x$ viene antes que $y$ pero $y$ no lo domina, tiene que ser necesariamente $x < y$.

Nuestro plan es entonces guardar todo el tiempo los índices del arreglo en donde se encuentran los elementos dominantes de la ventana actual, de izquierda a derecha. Notar que si tenemos los índices, tenemos también los elementos ya que el elemento en el lugar $i$ es $v[i]$. Como ya habíamos dicho, los únicos elementos que importan a la hora de buscar el mínimo son los dominantes, y esos de hecho están ordenados crecientemente, por lo tanto el mínimo de la ventana siempre es el primer elemento dominante, lo que llamaremos dominantes[0].

¿Cómo se ve afectada nuestra lista de dominantes al avanzarA? En este caso, se va un único elemento de la ventana, a la izquierda de todo. Hay dos posibilidades: si ese elemento era dominado, entonces absolutamente nada cambia. Si en cambio ese elemento era dominante, era necesariamente el primer dominante, y hay que eliminarlo de la lista. Podemos distinguir ambos casos mirando el índice, ya que el elemento que se va es el de índice $A$: si dominantes[0] == A, hay que borrar dominantes[0], y sino no.

Para poder borrar (e insertar) elementos de cualquiera de los dos extremos, guardaremos la lista de índices de los dominantes en un deque, que declaramos con deque<int> dominantes;.

Finalmente, lo único que falta es ver cómo resolver el avanzarB. En este caso, se agrega un único elemento al final de la ventana, en el índice $B$ del arreglo v. Como ya habíamos notado antes, este último elemento de la ventana siempre es dominante, o sea que sí o sí lo vamos a agregar con dominantes.push_back(B). Pero antes de eso, ¡hay que borrar todos los posibles elementos dominados que se generan!

Por ejemplo, supongamos que en la misma ventana que teníamos antes (con los dominantes marcados en verde):

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{green} 1 & \color{red}4 & \color{green}3 & 10 & 0\\ \hline & A=1 & & & & B=5 & \\ \end{array} \mbox{, mínimo=$1$}$$

Realizamos la operación avanzarB:

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{green} 1 & \color{red}4 & \color{green}3 & \color{green}{10} & 0\\ \hline & A=1 & & & & & B=6 \\ \end{array} \mbox{, mínimo=$1$}$$

En este caso, se agrega el 10 al final como nuevo dominante, pero ninguno de los anteriores cambia, porque el 10 no domina a nadie. Sin embargo, tras realizar otro avanzarB:

$$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{red} 1 & \color{red}4 & \color{red}3 & \color{red}{10} & \color{green}{0} & \\ \hline & A=1 & & & & & & B=0 \\ \end{array} \mbox{, mínimo=$0$}$$

¡Todos los elementos que había antes quedan dominados por el 0! Entonces, para procesar el avanzarB debemos sacar de dominantes todos los elementos que queden dominados por el elemento en la posición $B$, es decir, todos los que sean mayores o iguales que v[B]. Como los dominantes están siempre ordenados, estos elementos que hay que borrar están todos al final de la lista de dominantes. Por lo tanto, podemos ir haciendo dominantes.pop_back() continuamente, mientras el dominantes.back() sea el índice de un elemento que queda dominado por el de la posición $B$.

Lo anterior describe absolutamente todas las ideas de esta implementación. Recomendamos intentar programarla por uno mismo antes de mirar el código de ejemplo que sigue, como práctica de programación.

deque<int> dominantes;
int A=0, B=0;
void avanzarA()
{
    // Solo cambia algo si el que sacamos no estaba dominado.
    if (dominantes.front() == A)
        dominantes.pop_front();
    A++; 
}
void avanzarB()
{
    while (!dominantes.empty() && v[dominantes.back()] >= v[B])
        dominantes.pop_back();
    dominantes.push_back(B);
    B++; 
}
int minimoEnVentana()
{
    if (A == B)
        return INF; // VENTANA VACIA!!!
    else
        return v[dominantes.front()]; // dominantes.front() nos dice el indice
}

Salvo la operación de avanzarB, todas las demás realizan $O(1)$ operaciones $O(1)$, así que son de tiempo constante.

La complejidad de todas las operaciones resulta ser $O(1)$ amortizado, por exactamente la misma razón que en el ejemplo de pila con eliminación múltiple: lo único “caro” en avanzarB es el while para ir borrando los elementos dominados, pero cada elemento del arreglo original se puede borrar una única vez, y por lo tanto la complejidad total del algoritmo resultará ser $O(N)$, con lo cual el costo promedio por operación fue $O(1)$.

Ordenados en orden creciente de dificultad (subjetivamente):

• Sliding Window RMQ
• Jumpscotch
• Fila
• Pyramid