A pilha é a primeira estrutura de dados que todo mundo aprende e a última que as pessoas lembram de usar. O truque desta parte não é a pilha em si. É decidir o que você se recusa a guardar nela.
Todo programa abaixo está completo, rodou no .NET 10, e a saída foi colada da execução.
Padrão 21 — A pilha monotônica
Para cada elemento, encontre o próximo elemento à direita que seja maior.
Comparar cada um com tudo que vem depois é O(n²). A versão linear vem de uma única observação: enquanto você varre da esquerda para a direita, alguns elementos ainda esperam uma resposta. Guarde exatamente esses, e mais nada.
Quando um valor novo chega, ele responde todo elemento em espera menor que ele — possivelmente vários de uma vez — e depois entra na fila de espera também. Como cada um em espera só é resolvido pelo primeiro valor que o supera, a lista de espera é sempre decrescente de baixo para cima. É isso que “monotônica” significa aqui.
A pilha guarda os índices que ainda esperam uma resposta, e seus valores sempre decrescem de baixo para cima. Um valor novo maior que o topo resolve o topo — e possivelmente vários abaixo dele, todos no mesmo passo.
int[] a = [2, 1, 2, 4, 3];
int[] answer = new int[a.Length];
Array.Fill(answer, -1);
Stack<int> st = []; // indices, values DECREASING from bottom to top
for (int i = 0; i < a.Length; i++)
{
while (st.Count > 0 && a[st.Peek()] < a[i])
{
int j = st.Pop();
answer[j] = a[i];
Console.WriteLine($"i={i} a[i]={a[i]} resolves index {j} (value {a[j]}) -> next greater is {a[i]}");
}
st.Push(i);
Console.WriteLine($"i={i} a[i]={a[i]} push stack(values)=[{string.Join(",", st.Select(k => a[k]).Reverse())}]");
}
Console.WriteLine($"\nleft unresolved: [{string.Join(", ", st.Select(k => $"a[{k}]={a[k]}").Reverse())}] -> no greater element exists");
Console.WriteLine($"a = [{string.Join(", ", a)}]");
Console.WriteLine($"answer = [{string.Join(", ", answer)}]");Ele imprime:
i=0 a[i]=2 push stack(values)=[2]
i=1 a[i]=1 push stack(values)=[2,1]
i=2 a[i]=2 resolves index 1 (value 1) -> next greater is 2
i=2 a[i]=2 push stack(values)=[2,2]
i=3 a[i]=4 resolves index 2 (value 2) -> next greater is 4
i=3 a[i]=4 resolves index 0 (value 2) -> next greater is 4
i=3 a[i]=4 push stack(values)=[4]
i=4 a[i]=3 push stack(values)=[4,3]
left unresolved: [a[3]=4, a[4]=3] -> no greater element exists
a = [2, 1, 2, 4, 3]
answer = [4, 2, 4, -1, -1]Olhe o i=3. O valor 4 resolve dois elementos em espera num passo só, e nenhum é revisitado. Os dois que sobram na pilha no fim nunca receberam resposta, e está certo — não existe nada maior à direita deles.
O while aninhado parece quadrático. Não é: cada índice é empilhado exatamente uma vez e desempilhado no máximo uma vez, então o trabalho total da varredura inteira é no máximo 2n.
Custo: O(n) de tempo, O(n) de espaço.
Use quando a pergunta for próximo maior, anterior menor, quanto falta até algo mais alto, stock span, daily temperatures. Inverta a comparação para obter as variantes com menor.
Padrão 22 — O maior retângulo de um histograma
É o padrão acima justificando a sua existência.
Um retângulo que usa a barra i na altura cheia se estende à direita até encontrar uma barra mais baixa, e à esquerda até encontrar uma barra mais baixa. Então a largura dele é limitada pelo próximo elemento menor de cada lado — que é o padrão 21, rodado duas vezes.
A pilha monotônica dá as duas fronteiras em uma passada. Quando uma barra é desempilhada, o valor que está chegando é a fronteira direita dela, e o que estiver agora abaixo dela na pilha é a fronteira esquerda.
Todo retângulo é limitado pela primeira barra mais baixa de cada lado — que é a pergunta do próximo elemento menor, duas vezes. Por isso a pilha monotônica resolve: desempilhar uma barra dá as duas fronteiras de uma vez.
int[] h = [2, 1, 5, 6, 2, 3];
// The sentinel: a zero-height bar past the end forces every remaining bar to
// be resolved, so there is no separate drain loop after the scan.
int[] bars = [.. h, 0];
Stack<int> st = [];
int best = 0;
for (int i = 0; i < bars.Length; i++)
{
while (st.Count > 0 && bars[st.Peek()] >= bars[i])
{
int top = st.Pop();
int height = bars[top];
int left = st.Count == 0 ? -1 : st.Peek();
int width = i - left - 1;
int area = height * width;
Console.WriteLine($"i={i} pop bar {top} (height {height}) spans ({left}..{i}) exclusive width {width} area {area}");
best = Math.Max(best, area);
}
st.Push(i);
}
Console.WriteLine($"\nlargest rectangle: {best}");Ele imprime:
i=1 pop bar 0 (height 2) spans (-1..1) exclusive width 1 area 2
i=4 pop bar 3 (height 6) spans (2..4) exclusive width 1 area 6
i=4 pop bar 2 (height 5) spans (1..4) exclusive width 2 area 10
i=6 pop bar 5 (height 3) spans (4..6) exclusive width 1 area 3
i=6 pop bar 4 (height 2) spans (1..6) exclusive width 4 area 8
i=6 pop bar 1 (height 1) spans (-1..6) exclusive width 6 area 6
largest rectangle: 10Dois detalhes sustentam tudo.
A sentinela. Uma barra de altura zero é acrescentada depois do fim do array. Sem ela, as barras que ainda estiverem na pilha quando a varredura termina precisam de um laço de esvaziamento separado, com uma lógica ligeiramente diferente — e é nessa lógica duplicada que o bug mora. Uma barra de altura zero é mais baixa que tudo, então ela força cada barra restante a ser resolvida pelo laço principal.
A largura. É i - left - 1, onde left é o índice abaixo da barra desempilhada, não a própria barra desempilhada. As duas fronteiras são exclusivas: o trecho vai estritamente entre duas barras mais baixas. Um erro de um aqui dá uma resposta que parece plausível em entradas pequenas.
Custo: O(n) de tempo, O(n) de espaço.
Use quando você precisa do maior retângulo, do maior quadrado em uma matriz binária (rode isto uma vez por linha), ou de qualquer pergunta do tipo “até onde isto se estende antes de algo bloquear”.
Padrão 23 — Parênteses balanceados
O uso mais simples de uma pilha, e vale incluir porque é nos detalhes que dá errado.
static bool Valid(string s)
{
Dictionary<char, char> pairs = new() { [')'] = '(', [']'] = '[', ['}'] = '{' };
Stack<char> st = [];
foreach (char c in s)
{
if (pairs.ContainsValue(c)) { st.Push(c); continue; }
if (!pairs.TryGetValue(c, out char open)) continue; // not a bracket
if (st.Count == 0 || st.Pop() != open) return false;
}
return st.Count == 0;
}
foreach (string s in new[] { "{[()]}", "([)]", "(((", "", "a(b[c]d)e" })
Console.WriteLine($"{$"\"{s}\"",12} -> {Valid(s)}");Ele imprime:
"{[()]}" -> True
"([)]" -> False
"(((" -> False
"" -> True
"a(b[c]d)e" -> TrueOs dois casos que as pessoas esquecem estão nessa saída. "(((" falha não porque achou um par errado, mas porque a pilha não está vazia no fim — todo abridor precisa de um par. E "" é válido, e isso cai da mesma verificação em vez de precisar de um caso especial.
"([)]" é a razão de a pilha ser necessária. Um contador para cada tipo de delimitador diria que é válido: um (, um ), um [, um ]. Aninhamento é uma questão de ordem, e só uma pilha registra ordem.
Custo: O(n) de tempo, O(n) de espaço.
Use quando algo aninha — delimitadores, tags, parsing de expressão, histórico de desfazer.
Padrão 24 — Uma pilha que conhece o próprio mínimo
Informe o mínimo de tudo que está na pilha, em O(1), enquanto empilhamentos e desempilhamentos continuam acontecendo.
Manter uma única variável min falha no desempilhamento: quando o mínimo é removido, o segundo menor tem que ser encontrado de novo, e isso é O(n).
A correção é parar de tratar o mínimo como um fato único sobre a pilha inteira. Guarde, junto de cada elemento, o mínimo de tudo que está nele ou abaixo dele.
Um int a mais por elemento compra Min() em O(1). Ele sobrevive ao desempilhamento porque o mínimo de cada entrada foi calculado a partir do que estava abaixo dela, nunca do que veio depois.
// Each entry carries the minimum of everything at or below it. That makes Min
// a peek, and costs one extra int per element.
Stack<(int value, int min)> st = [];
void Push(int v)
{
int min = st.Count == 0 ? v : Math.Min(v, st.Peek().min);
st.Push((v, min));
Console.WriteLine($"push {v,3} min is now {min,3} stack=[{string.Join(" ", st.Select(x => $"{x.value}/{x.min}").Reverse())}]");
}
foreach (int v in new[] { 5, 2, 7, 2, 9 }) Push(v);
Console.WriteLine();
while (st.Count > 0)
{
var (v, m) = st.Peek();
Console.WriteLine($"top {v,3} Min() = {m,3}");
st.Pop();
}Ele imprime:
push 5 min is now 5 stack=[5/5]
push 2 min is now 2 stack=[5/5 2/2]
push 7 min is now 2 stack=[5/5 2/2 7/2]
push 2 min is now 2 stack=[5/5 2/2 7/2 2/2]
push 9 min is now 2 stack=[5/5 2/2 7/2 2/2 9/2]
top 9 Min() = 2
top 2 Min() = 2
top 7 Min() = 2
top 2 Min() = 2
top 5 Min() = 5Desempilhar não exige recálculo nenhum, e vale dizer o motivo com todas as letras: o mínimo de cada entrada foi calculado a partir do que estava abaixo dela, nunca do que veio depois. Remover entradas posteriores não pode invalidá-lo.
O custo é um int a mais por elemento. Olhe a sequência de desempilhamento na saída — o 5 informa corretamente o próprio mínimo como 5 depois que tudo acima dele sai.
Custo: O(1) para push, pop e mínimo. O(n) de espaço.
Use quando você precisa de um agregado corrente que sobrevive ao desempilhamento. A mesma forma funciona para máximo, ou para o mdc.
Padrão 25 — O container que o C# não traz
Stack<T> e Queue<T> existem e são bons. O que não existe é um deque sobre array — não há ArrayDeque.
LinkedList<T> resolve, e é o que o máximo em janela deslizante da parte 2 usou. Ela também aloca um objeto de nó para cada elemento, e em tamanhos de entrada de maratona essa alocação aparece. Um ring buffer sobre um único array não aloca, e é curto o bastante para você digitar de memória.
O C# traz Stack<T> e Queue<T>, mas nenhum deque sobre array. LinkedList<T> preenche a lacuna e aloca um objeto de nó por elemento; um ring buffer aloca um array, e tem umas vinte linhas.
var d = new Deque(8);
d.PushBack(1); d.PushBack(2); d.PushBack(3);
Console.WriteLine($"pushed 1,2,3 at the back {d}");
d.PushFront(0);
Console.WriteLine($"pushed 0 at the front {d} (head wrapped round to the end of the array)");
Console.WriteLine($"first={d.First} last={d.Last}");
Console.WriteLine($"popFront -> {d.PopFront()} {d}");
Console.WriteLine($"popBack -> {d.PopBack()} {d}");
Console.WriteLine();
Stack<int> st = []; st.Push(1); st.Push(2);
Queue<int> q = []; q.Enqueue(1); q.Enqueue(2);
Console.WriteLine($"Stack<int> Peek={st.Peek()} LIFO — Push / Pop / Peek");
Console.WriteLine($"Queue<int> Peek={q.Peek()} FIFO — Enqueue / Dequeue / Peek");
Console.WriteLine($"Deque {d} both ends, one array, no per-item allocation");
// In a file-based app, type declarations come AFTER the top-level statements.
class Deque(int cap)
{
readonly int[] buf = new int[cap];
int head = 0, count = 0;
public int Count => count;
public int First => buf[head];
public int Last => buf[(head + count - 1) % buf.Length];
public void PushBack(int v) { buf[(head + count) % buf.Length] = v; count++; }
public void PushFront(int v) { head = (head - 1 + buf.Length) % buf.Length; buf[head] = v; count++; }
public int PopFront() { int v = buf[head]; head = (head + 1) % buf.Length; count--; return v; }
public int PopBack() { count--; return buf[(head + count) % buf.Length]; }
public override string ToString()
{
var parts = new List<int>();
for (int i = 0; i < count; i++) parts.Add(buf[(head + i) % buf.Length]);
return "[" + string.Join(", ", parts) + "]";
}
}Ele imprime:
pushed 1,2,3 at the back [1, 2, 3]
pushed 0 at the front [0, 1, 2, 3] (head wrapped round to the end of the array)
first=0 last=3
popFront -> 0 [1, 2, 3]
popBack -> 3 [1, 2]
Stack<int> Peek=2 LIFO — Push / Pop / Peek
Queue<int> Peek=1 FIFO — Enqueue / Dequeue / Peek
Deque [1, 2] both ends, one array, no per-item allocationA ideia toda é % buf.Length. Empilhar na frente move o head para trás e o faz dar a volta até o fim do array; nada é deslocado, e os elementos deixam de estar guardados na ordem lógica. O ToString percorre head, head+1, … módulo o comprimento para recuperá-la.
Repare no + buf.Length do PushFront. Em C#, -1 % 8 é -1, não 7 — o operador % mantém o sinal do operando da esquerda. Omitir esse termo dá um índice negativo, e a exceção que ele lança fica bem longe da linha que a causou.
Custo: O(1) nas duas pontas, um array alocado uma vez.
Use quando você precisa das duas pontas — máximo em janela deslizante, 0-1 BFS na parte 8, ou qualquer BFS em que algumas arestas não custam nada.
O que lembrar
-
Uma pilha monotônica guarda só os elementos que ainda esperam uma resposta. Eles saem ordenados porque cada um é resolvido pelo primeiro valor que o supera.
-
O
whileaninhado continua linear. Cada índice entra uma vez e sai uma vez. Repita isso para você mesmo em vez de confiar no formato do código. -
Use uma sentinela em vez de um laço de esvaziamento. Uma barra de altura zero depois do fim força o laço principal a resolver tudo, e remove a lógica duplicada onde os bugs moram.
-
As larguras no histograma são exclusivas dos dois lados.
i - left - 1, comleftlido da pilha depois do desempilhamento. -
Um delimitador não fechado é uma pilha não vazia no fim. É essa verificação que faz
"((("falhar e""passar, sem casos especiais. -
Uma pilha com mínimo guarda o mínimo junto de cada elemento, não uma vez só. Ela sobrevive ao desempilhamento porque só olhou para baixo.
-
O C# não tem deque sobre array, e
-1 % 8é-1. Some o comprimento antes de tirar o módulo, sempre.
A parte 6 é sobre os containers propriamente ditos: dicionários, comparadores customizados, compressão de coordenadas, e PriorityQueue<TElement, TPriority> — que só chegou no .NET 6, e que muito material antigo de maratona em C# ainda contorna.