• 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)$.

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