• 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

La complejidad resulta ser $O(1)$ amortizado, por exactamente la misma razón que en el ejemplo de pila con eliminación múltiple.

Ordenados en orden creciente de dificultad (subjetivamente):

• Sliding Window RMQ
• Jumpscotch
• Fila
• Pyramid