Ventana deslizante en C#

La parte 1 movía dos punteros uno hacia el otro. Aquí los dos se mueven a la derecha, y lo que importa es la brecha entre ellos. Esa brecha es la ventana, y toda la familia se reduce a dos preguntas: cuándo la hago crecer y cuándo la encojo.

Todos los programas de abajo están completos, se ejecutaron en .NET 10, y su salida está pegada de la corrida.

Por qué vale la pena

Toma la suma más grande de k valores consecutivos. La versión obvia suma cada ventana desde cero. Cuenta las sumas:

// How many additions each approach needs. No timing — just the work done.
Console.WriteLine($"{"n",8}  {"k",6}  {"recompute",14}  {"slide",10}");

foreach ((int n, int k) in new[] { (8, 3), (1_000, 100), (100_000, 1_000) })
{
    long recompute = (long)(n - k + 1) * k;
    long slide = k + (long)(n - k) * 2;
    Console.WriteLine($"{n,8}  {k,6}  {recompute,14:N0}  {slide,10:N0}");
}

Imprime:

       n       k       recompute       slide
       8       3              18          13
    1000     100          90,100       1,900
  100000    1000      99,001,000     199,000

Con ocho elementos, 18 contra 13 no es nada. Con cien mil, son noventa y nueve millones contra doscientos mil, y solo uno de los dos termina dentro del límite de tiempo.

La razón es que las ventanas vecinas se traslapan casi por completo. Recalcular tira ese traslape a la basura cada vez.

Patrón 6 — La ventana fija

La ventana siempre mide exactamente k. Deslízala un paso: un valor sale por la izquierda, otro entra por la derecha, y el total corriente se corrige con una resta y una suma. Los otros k-2 valores nunca se tocan.

int[] a = [3, 1, 4, 1, 5, 9, 2, 6];
int k = 3;

int win = 0;
for (int i = 0; i < k; i++) win += a[i];

int best = win, bestAt = 0;
Console.WriteLine($"window [0..{k - 1}]              sum = {win}");

for (int r = k; r < a.Length; r++)
{
    int leaving = a[r - k], entering = a[r];
    win += entering - leaving;
    if (win > best) { best = win; bestAt = r - k + 1; }
    Console.WriteLine($"window [{r - k + 1}..{r}]  -{leaving} +{entering}  sum = {win}");
}

Console.WriteLine($"\nbest = {best}, starting at index {bestAt}: [{string.Join(", ", a[bestAt..(bestAt + k)])}]");

Imprime:

window [0..2]              sum = 8
window [1..3]  -3 +1  sum = 6
window [2..4]  -1 +5  sum = 10
window [3..5]  -4 +9  sum = 15
window [4..6]  -1 +2  sum = 16
window [5..7]  -5 +6  sum = 17

best = 17, starting at index 5: [9, 2, 6]

Costo: O(n) en tiempo, O(1) en espacio.

Úsalo cuando el problema te fija el tamaño de la ventana — toda subcadena de longitud k, cualesquiera k días consecutivos. Si puedes mantener la respuesta de una ventana en O(1) mientras se desliza, este es el patrón.

Patrón 7 — Crece hasta que se rompa, quédate con la más larga

Ahora el tamaño de la ventana no te lo dan; es lo que estás buscando. Encuentra el tramo más largo sin caracteres repetidos.

La regla se invierte: crece siempre por la derecha, y encoge por la izquierda solo cuando la ventana se vuelve inválida. La respuesta es la ventana válida más grande que hayas visto.

Lo interesante es lo que significa «encoger» aquí. Al ver una repetición, no avanzas el borde izquierdo de a un paso — lo saltas directo más allá de la ocurrencia anterior. Y ese salto tiene una trampa.

string s = "abba";

Dictionary<char, int> lastSeen = [];
int lo = 0, best = 0, bestAt = 0;

for (int r = 0; r < s.Length; r++)
{
    char c = s[r];

    if (lastSeen.TryGetValue(c, out int prev) && prev >= lo)
    {
        Console.WriteLine($"r={r} '{c}'  seen at {prev}, and {prev} >= lo({lo})  ->  lo jumps to {prev + 1}");
        lo = prev + 1;
    }
    else if (lastSeen.TryGetValue(c, out int old))
    {
        Console.WriteLine($"r={r} '{c}'  seen at {old}, but {old} < lo({lo})  ->  it is OUTSIDE the window, lo stays");
    }
    else
    {
        Console.WriteLine($"r={r} '{c}'  never seen                        ->  lo stays {lo}");
    }

    lastSeen[c] = r;
    int len = r - lo + 1;
    if (len > best) { best = len; bestAt = lo; }
    Console.WriteLine($"        window [{lo}..{r}] = \"{s[lo..(r + 1)]}\"  length {len}");
}

Console.WriteLine($"\nlongest = {best}, \"{s.Substring(bestAt, best)}\"");

Imprime:

r=0 'a'  never seen                        ->  lo stays 0
        window [0..0] = "a"  length 1
r=1 'b'  never seen                        ->  lo stays 0
        window [0..1] = "ab"  length 2
r=2 'b'  seen at 1, and 1 >= lo(0)  ->  lo jumps to 2
        window [2..2] = "b"  length 1
r=3 'a'  seen at 0, but 0 < lo(2)  ->  it is OUTSIDE the window, lo stays
        window [2..3] = "ba"  length 2

longest = 2, "ab"

Lee la línea r=3. La 'a' se vio por última vez en el índice 0, pero la ventana empieza en 2, así que esa 'a' quedó atrás y ya no está en la ventana. Saltar lo a 0 + 1 movería el borde izquierdo hacia atrás, y la ventana empezaría a contar en silencio caracteres que ya había descartado.

lo nunca debe disminuir. Todo patrón de ventana que salta el borde izquierdo necesita una guarda que lo diga.

Quita la prueba prev >= lo y "abba" reporta 3. Es un bug de una sola palabra, y entradas pequeñas como "abcabc" no lo detectan.

Costo: O(n) en tiempo — cada puntero solo se mueve a la derecha. O(k) en espacio para el diccionario, donde k es el tamaño del alfabeto.

Úsalo cuando el problema pide la ventana más larga que cumple una condición, y romper esa condición se puede reparar quitando elementos por la izquierda.

Patrón 8 — Encoge mientras siga cumpliendo, quédate con la más corta

La imagen especular. Encuentra la ventana más corta cuya suma llegue al menos a un objetivo.

Crecer hace la suma más grande, así que crecer arregla una ventana inválida. Eso significa que el bucle while se pasa al otro lado: en cuanto la ventana sí es válida, encógela mientras siga siéndolo, anotando la longitud cada vez.

int[] a = [2, 3, 1, 2, 4, 3];
int target = 7;

int lo = 0, sum = 0, best = int.MaxValue, bestAt = -1;

for (int r = 0; r < a.Length; r++)
{
    sum += a[r];
    Console.WriteLine($"r={r}  +{a[r]}  window [{lo}..{r}] sum={sum}");

    while (sum >= target)
    {
        int len = r - lo + 1;
        if (len < best) { best = len; bestAt = lo; }
        Console.WriteLine($"        sum {sum} >= {target}, length {len}  ->  shrink: drop a[{lo}]={a[lo]}");
        sum -= a[lo];
        lo++;
    }
}

Console.WriteLine(best == int.MaxValue
    ? "\nno window reaches the target"
    : $"\nshortest = {best}, starting at {bestAt}: [{string.Join(", ", a[bestAt..(bestAt + best)])}]");

Imprime:

r=0  +2  window [0..0] sum=2
r=1  +3  window [0..1] sum=5
r=2  +1  window [0..2] sum=6
r=3  +2  window [0..3] sum=8
        sum 8 >= 7, length 4  ->  shrink: drop a[0]=2
r=4  +4  window [1..4] sum=10
        sum 10 >= 7, length 4  ->  shrink: drop a[1]=3
        sum 7 >= 7, length 3  ->  shrink: drop a[2]=1
r=5  +3  window [3..5] sum=9
        sum 9 >= 7, length 3  ->  shrink: drop a[3]=2
        sum 7 >= 7, length 2  ->  shrink: drop a[4]=4

shortest = 2, starting at 4: [4, 3]

El while hace el trabajo de verdad, y tiene que ser un while, no un if. En r=4 la ventana encoge dos veces seguidas. Un if encogería una sola vez, dejaría una ventana válida pero no mínima, y devolvería 3 en vez de 2 sin decir nada.

La más larga quiere while (invalid) shrink; y anota después. La más corta quiere while (valid) { record; shrink; }. Esas dos líneas son la diferencia entre los dos patrones, y todo lo demás es el mismo código.

Costo: O(n) — lo y r recorren el arreglo una vez cada uno, así que el bucle anidado sigue siendo lineal.

Úsalo cuando el problema dice más corta, más pequeña o longitud mínima, y todos los valores empujan la cantidad en la misma dirección. Esa última condición importa: con números negativos en el arreglo, crecer ya no garantiza una suma mayor, la regla de encoger deja de ser válida, y necesitas sumas de prefijos — que es la parte 3.

Patrón 9 — Cuenta «a lo más», resta para obtener «exactamente»

Cuenta los subarreglos que contienen exactamente K valores distintos.

Intenta deslizar eso directamente y te atoras. Si una ventana tiene muy pocos valores distintos, no hay movimiento que la repare: encoger por la izquierda no agrega variedad. La condición no va en un solo sentido, así que la ventana no tiene de dónde agarrarse.

«A lo más K» sí va en un solo sentido. Demasiados valores distintos siempre se arregla encogiendo. Así que cuenta eso en su lugar, dos veces:

exactly K  =  (at most K)  −  (at most K−1)

La otra mitad de este patrón es el conteo mismo. Para una ventana [lo..r] que es válida, toda ventana que termina en r y empieza en cualquier punto de lo..r también es válida — porque quitar elementos por la izquierda solo puede reducir la cuenta de distintos. Son r - lo + 1 ventanas, sumadas de un paso en vez de enumeradas.

int[] a = [1, 2, 1, 2, 3];
int k = 2;

// Windows with AT MOST k distinct values. This one is easy to slide, because
// "too many distinct" is fixable by shrinking from the left.
static long AtMost(int[] a, int k, string label)
{
    Dictionary<int, int> count = [];
    long total = 0;
    int lo = 0;

    for (int r = 0; r < a.Length; r++)
    {
        count[a[r]] = count.GetValueOrDefault(a[r]) + 1;

        while (count.Count > k)
        {
            if (--count[a[lo]] == 0) count.Remove(a[lo]);
            lo++;
        }

        // Every window ending at r and starting at lo..r is valid: that is r-lo+1 of them.
        total += r - lo + 1;
    }

    Console.WriteLine($"{label}: {total}");
    return total;
}

long atMostK = AtMost(a, k, $"at most {k} distinct");
long atMostK1 = AtMost(a, k - 1, $"at most {k - 1} distinct");

Console.WriteLine($"\nexactly {k} distinct = {atMostK} - {atMostK1} = {atMostK - atMostK1}");

Imprime:

at most 2 distinct: 12
at most 1 distinct: 5

exactly 2 distinct = 12 - 5 = 7

Costo: O(n), dos veces, así que sigue siendo O(n).

Úsalo cuando la palabra es exactamente. Aparece con exactamente K distintos, exactamente K números impares, sumas dentro de un rango. La jugada siempre es la misma: encuentra la versión de un solo sentido de la pregunta, cuéntala dos veces, resta.

Patrón 10 — El máximo de la ventana, sin volver a recorrerla

Reporta el máximo de cada ventana de tamaño k. Volver a recorrer cada ventana es O(nk), y un heap te da O(n log k) pero necesita borrado perezoso para manejar los valores que se salen de la ventana.

Hay una respuesta O(n), y sale de una sola observación. Si a[i] es menor que algún a[j] con j > i, entonces a[i] está acabado. Toda ventana futura que contenga a i también contiene a j, y j es a la vez mayor y más nuevo. a[i] nunca puede volver a ser un máximo, así que nunca hace falta guardarlo.

Guarda solo los valores que siguen siendo candidatos. Quedan en orden decreciente, del frente hacia atrás.

int[] a = [1, 3, -1, -3, 5, 3, 6, 7];
int k = 3;

LinkedList<int> dq = [];        // holds INDICES, values decreasing front to back
List<int> answer = [];

for (int r = 0; r < a.Length; r++)
{
    while (dq.Count > 0 && dq.First!.Value <= r - k)
    {
        Console.WriteLine($"r={r}  index {dq.First.Value} fell out of the window   drop from front");
        dq.RemoveFirst();
    }

    while (dq.Count > 0 && a[dq.Last!.Value] <= a[r])
    {
        Console.WriteLine($"r={r}  a[{dq.Last.Value}]={a[dq.Last.Value]} <= a[{r}]={a[r]}   it can never win again, drop from back");
        dq.RemoveLast();
    }

    dq.AddLast(r);

    if (r >= k - 1)
    {
        answer.Add(a[dq.First!.Value]);
        Console.WriteLine($"r={r}  window [{r - k + 1}..{r}]  deque=[{string.Join(",", dq)}]  max = a[{dq.First.Value}] = {a[dq.First.Value]}");
    }
}

Console.WriteLine($"\nmaxima: [{string.Join(", ", answer)}]");

Imprime:

r=1  a[0]=1 <= a[1]=3   it can never win again, drop from back
r=2  window [0..2]  deque=[1,2]  max = a[1] = 3
r=3  window [1..3]  deque=[1,2,3]  max = a[1] = 3
r=4  index 1 fell out of the window   drop from front
r=4  a[3]=-3 <= a[4]=5   it can never win again, drop from back
r=4  a[2]=-1 <= a[4]=5   it can never win again, drop from back
r=4  window [2..4]  deque=[4]  max = a[4] = 5
r=5  window [3..5]  deque=[4,5]  max = a[4] = 5
r=6  a[5]=3 <= a[6]=6   it can never win again, drop from back
r=6  a[4]=5 <= a[6]=6   it can never win again, drop from back
r=6  window [4..6]  deque=[6]  max = a[6] = 6
r=7  a[6]=6 <= a[7]=7   it can never win again, drop from back
r=7  window [5..7]  deque=[7]  max = a[7] = 7

maxima: [3, 3, 5, 5, 6, 7]

Dos detalles que vale la pena nombrar. El deque guarda índices, no valores, porque hay que revisar si el frente ya se salió de la ventana, y esa es una pregunta sobre posición. Y el frente siempre es la respuesta: es el candidato sobreviviente más grande, y todo lo que antes estaba delante de él se descartó por ser menor.

Los bucles while anidados parecen cuadráticos y no lo son. Cada índice se agrega exactamente una vez y se quita a lo más una vez, así que el trabajo total en todo el recorrido está acotado por 2n.

Costo: O(n) en tiempo, O(k) en espacio.

Úsalo cuando necesitas un mínimo o un máximo corriente sobre una ventana fija. La misma estructura, con la comparación invertida, te da el mínimo corriente.

Qué recordar

• Recalcular cada ventana tira el traslape a la basura. En vez de eso, corrige el valor corriente con lo que sale y lo que entra — dos operaciones en lugar de k.

• La más larga y la más corta son el mismo código con el while en lados opuestos. La más larga: encoge mientras sea inválida, después anota. La más corta: mientras sea válida, anota y después encoge.

• lo nunca debe moverse hacia atrás. Todo patrón que salta el borde izquierdo más allá de una ocurrencia anterior necesita la guarda prev >= lo, y "abba" es la entrada más pequeña que lo demuestra.

• «Exactamente K» no se puede deslizar. Que haya muy pocos no se arregla desde la izquierda. Cuenta «a lo más K» dos veces y resta.

• Una ventana válida [lo..r] aporta r - lo + 1 subarreglos, no uno. Contar ventanas de a una es la otra forma en que la gente vuelve cuadrática una solución lineal.

• El deque monótono descarta todo lo que sea menor y más viejo. Guarda índices, el frente es la respuesta, y cada índice entra y sale una vez — que es todo el argumento de O(n).

La parte 3 cubre qué hacer cuando el truco de la ventana deja de funcionar: números negativos, rangos arbitrarios y actualizaciones aplicadas a tramos enteros de una vez. Sumas de prefijos y arreglos de diferencias.