A parte 1 movia dois ponteiros um na direção do outro. Aqui os dois andam para a direita, e o que importa é o espaço entre eles. Esse espaço é a janela, e a família inteira se resume a duas perguntas: quando eu faço ela crescer, e quando eu encolho.
Todo programa abaixo está completo, rodou no .NET 10, e a saída dele foi colada da execução.
Por que vale o esforço
Pegue a maior soma de k valores consecutivos. A versão óbvia soma cada janela do zero. Conte as adições:
// 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}");
}Ele imprime:
n k recompute slide
8 3 18 13
1000 100 90,100 1,900
100000 1000 99,001,000 199,000Com oito elementos, 18 contra 13 não é nada. Com cem mil, são noventa e nove milhões contra duzentos mil, e só um dos dois termina dentro do limite de tempo.
O motivo é que janelas vizinhas se sobrepõem quase por completo. Recalcular joga essa sobreposição fora toda vez.
Padrão 6 — A janela fixa
A janela tem sempre exatamente k de largura. Deslize um passo: um valor sai pela esquerda, um chega pela direita, e o total corrente é corrigido com uma subtração e uma adição. Os outros k-2 valores nunca são tocados.
A janela nunca é somada de novo. Um valor sai pela esquerda (vermelho), um chega pela direita, e a soma corrente é corrigida com duas operações em vez de k.
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)])}]");Ele 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]Custo: O(n) de tempo, O(1) de espaço.
Use quando o problema já fixa o tamanho da janela para você — toda substring de tamanho k, quaisquer k dias consecutivos. Se você consegue manter a resposta de uma janela em O(1) enquanto ela desliza, o padrão é esse.
Padrão 7 — Cresça até quebrar, guarde a maior
Agora o tamanho da janela não é dado; ele é o que você está buscando. Ache o maior trecho sem caractere repetido.
A regra vira: cresça pela direita sempre, e encolha pela esquerda só quando a janela ficou inválida. A resposta é a maior janela válida já vista.
A parte interessante é o que “encolher” significa aqui. Ao ver uma repetição, você não move a borda esquerda de um em um — você pula direto para depois da ocorrência anterior. E esse pulo tem uma armadilha dentro.
A armadilha é a última linha. ‘a’ foi visto no índice 0, mas o índice 0 não está mais na janela, então a borda esquerda não pode voltar para ele. Sem a guarda `prev >= lo`, lo anda para trás e a janela cresce sem controle.
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)}\"");Ele 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"Leia a linha r=3. 'a' foi visto por último no índice 0, mas a janela começa em 2, então esse 'a' ficou para trás e não está mais na janela. Pular lo para 0 + 1 moveria a borda esquerda para trás, e a janela começaria a contar, sem avisar, caracteres que já tinha descartado.
lonunca pode diminuir. Todo padrão de janela que pula a borda esquerda precisa de uma guarda dizendo isso.
Tire o teste prev >= lo e "abba" devolve 3. É um bug de uma palavra, e entradas pequenas como "abcabc" não pegam ele.
Custo: O(n) de tempo — cada ponteiro só anda para a direita. O(k) de espaço para o mapa, onde k é o tamanho do alfabeto.
Use quando o problema pede a maior janela que satisfaz uma condição, e quebrar essa condição pode ser consertado tirando elementos da esquerda.
Padrão 8 — Encolha enquanto ainda vale, guarde a menor
A imagem espelhada. Ache a menor janela cuja soma é pelo menos um alvo.
Crescer aumenta a soma, então crescer conserta uma janela inválida. Ou seja, o laço while muda de lado: assim que a janela é válida, encolha ela enquanto continuar válida, anotando o comprimento a cada passo.
Cresça pela direita até a janela ficar válida, depois encolha pela esquerda enquanto ela continuar válida. A menor resposta aparece no ponto em que encolher quebraria.
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)])}]");Ele 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]O while é quem faz o trabalho de verdade, e ele tem que ser um while, não um if. Em r=4 a janela encolhe duas vezes seguidas. Um if encolheria uma vez, deixaria uma janela válida mas não mínima, e devolveria 3 em vez de 2, sem avisar.
Maior quer while (inválida) encolhe; e anota depois. Menor quer while (válida) { anota; encolhe; }. Essas duas linhas são a diferença entre os dois padrões, e todo o resto é o mesmo código.
Custo: O(n) — lo e r percorrem o array uma vez cada, então o laço aninhado ainda é linear.
Use quando o problema diz menor, mínima ou comprimento mínimo, e todos os valores empurram a grandeza para o mesmo lado. Essa última condição importa: com números negativos no array, crescer não garante mais uma soma maior, a regra de encolher deixa de valer, e você precisa de somas de prefixos — que é a parte 3.
Padrão 9 — Conte “no máximo”, subtraia para ter “exatamente”
Conte os subarrays que contêm exatamente K valores distintos.
Tente deslizar isso direto e você trava. Se uma janela tem poucos valores distintos, não existe movimento que conserte: encolher pela esquerda não adiciona variedade. A condição não é de um lado só, então a janela não tem em que se apoiar.
“No máximo K” é de um lado só. Distintos demais sempre se conserta encolhendo. Então conte isso, duas vezes:
exactly K = (at most K) − (at most K−1)“No máximo K” desliza limpo porque valores distintos demais dá para consertar encolhendo pela esquerda. “Exatamente K” não — não existe movimento que conserte poucos demais. Então conte a coisa fácil duas vezes e subtraia.
A outra metade desse padrão é a contagem em si. Para uma janela [lo..r] que é válida, toda janela que termina em r e começa em qualquer ponto de lo..r também é válida — porque tirar elementos da esquerda só reduz a contagem de distintos. São r - lo + 1 janelas, somadas de uma vez em 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}");Ele imprime:
at most 2 distinct: 12
at most 1 distinct: 5
exactly 2 distinct = 12 - 5 = 7Custo: O(n), duas vezes, então ainda O(n).
Use quando a palavra é exatamente. Aparece em exatamente K distintos, exatamente K números ímpares, somas dentro de um intervalo. A jogada é sempre a mesma: ache a versão de um lado só da pergunta, conte duas vezes, subtraia.
Padrão 10 — O máximo da janela, sem revarrer
Informe o máximo de cada janela de tamanho k. Revarrer cada janela é O(nk), e um heap te dá O(n log k) mas precisa de remoção preguiçosa para lidar com os valores que saem da janela.
Existe uma resposta O(n), e ela vem de uma observação. Se a[i] é menor que algum a[j] com j > i, então a[i] está acabado. Toda janela futura que contém i também contém j, e j é maior e mais novo. a[i] nunca mais pode ser um máximo, então nem precisa ser guardado.
Guarde só os valores que ainda são candidatos. Eles ficam decrescentes, da frente para o fim.
O deque guarda índices, e os valores deles sempre decrescem da frente para o fim. Cada índice entra uma vez e sai uma vez, e é por isso que a varredura inteira é O(n) apesar dos laços while internos.
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)}]");Ele 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]Dois detalhes que merecem nome. O deque guarda índices, não valores, porque a frente precisa ser checada para ver se saiu da janela, e isso é uma pergunta sobre posição. E a frente é sempre a resposta: é o maior candidato sobrevivente, e tudo que já esteve na frente dele foi descartado por ser menor.
Os laços while aninhados parecem quadráticos e não são. Todo índice é adicionado exatamente uma vez e removido no máximo uma vez, então o trabalho total da varredura inteira é limitado por 2n.
Custo: O(n) de tempo, O(k) de espaço.
Use quando você precisa de um mínimo ou máximo corrente sobre uma janela fixa. A mesma estrutura, com a comparação invertida, dá o mínimo corrente.
O que lembrar
-
Recalcular cada janela joga fora a sobreposição. Em vez disso, corrija o valor corrente com o que sai e o que chega — duas operações em vez de
k. -
Maior e menor são o mesmo código com o
whileem lados opostos. Maior: encolha enquanto inválida, depois anote. Menor: enquanto válida, anote e depois encolha. -
lonunca pode andar para trás. Todo padrão que pula a borda esquerda para depois de uma ocorrência anterior precisa da guardaprev >= lo, e"abba"é a menor entrada que prova isso. -
“Exatamente K” não dá para deslizar. Poucos demais não tem conserto pela esquerda. Conte “no máximo K” duas vezes e subtraia.
-
Uma janela válida
[lo..r]contribui comr - lo + 1subarrays, não um. Contar janelas de uma em uma é o outro jeito de as pessoas transformarem uma solução linear em quadrática. -
O deque monotônico descarta tudo que é menor e mais velho. Ele guarda índices, a frente é a resposta, e cada índice entra e sai uma vez — que é o argumento O(n) inteiro.
A parte 3 cobre o que fazer quando o truque da janela para de funcionar: números negativos, intervalos arbitrários, e atualizações aplicadas a trechos inteiros de uma vez. Somas de prefixos e arrays de diferenças.