Una pila es la primera estructura de datos que cualquiera aprende y la última que a la gente se le ocurre usar. El truco de esta parte no es la pila en sí. Es decidir qué te niegas a guardar en ella.
Todos los programas de abajo están completos, se ejecutaron en .NET 10, y su salida está pegada de la ejecución.
Patrón 21 — La pila monótona
Para cada elemento, encuentra el siguiente elemento a su derecha que sea más grande.
Comparar cada uno contra todo lo que viene después es O(n²). La versión lineal sale de una sola observación: mientras recorres de izquierda a derecha, algunos elementos siguen esperando una respuesta. Guarda exactamente esos, y nada más.
Cuando llega un valor nuevo, responde a todos los elementos en espera que son menores que él — posiblemente varios de una vez — y luego se suma él mismo a la fila de los que esperan. Como a cada uno lo resuelve solo el primer valor que lo supera, la lista de espera siempre va decreciendo de abajo hacia arriba. Eso es lo que significa «monótona» aquí.
La pila guarda los índices que aún esperan una respuesta, y sus valores siempre decrecen de abajo hacia arriba. Un valor nuevo más alto que la cima lo resuelve — y posiblemente varios debajo, todos en el mismo paso.
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)}]");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]Fíjate en i=3. El valor 4 resuelve dos elementos en espera en un solo paso, y ninguno se vuelve a mirar. Los dos que quedan en la pila al final nunca recibieron respuesta, y está exactamente bien — no existe nada mayor a su derecha.
El while anidado parece cuadrático. No lo es: cada índice entra exactamente una vez y sale a lo sumo una vez, así que el trabajo total en todo el recorrido es a lo sumo 2n.
Costo: O(n) en tiempo, O(n) en espacio.
Úsalo cuando la pregunta sea siguiente mayor, anterior menor, cuánto falta hasta algo más alto, stock span, daily temperatures. Invierte la comparación para obtener las variantes con el menor.
Patrón 22 — El rectángulo más grande en un histograma
Este es el patrón de arriba, ganándose el sueldo.
Un rectángulo que usa la barra i a toda su altura se extiende a la derecha hasta encontrar una barra más baja, y a la izquierda hasta encontrar una barra más baja. Así que su ancho está limitado por el siguiente elemento menor de cada lado — que es el patrón 21, ejecutado dos veces.
La pila monótona da los dos límites en una sola pasada. Cuando una barra sale de la pila, el valor que llega es su límite derecho, y lo que ahora queda debajo en la pila es su límite izquierdo.
Cada rectángulo está limitado por la primera barra más baja de cada lado — que es la pregunta del siguiente elemento menor, dos veces. Por eso la pila monótona lo resuelve: sacar una barra te dice los dos límites a la 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}");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: 10Dos detalles cargan con todo el peso.
El centinela. Se agrega una barra de altura cero después del final del arreglo. Sin ella, las barras que queden en la pila al terminar el recorrido necesitan un bucle de vaciado aparte con una lógica un poco distinta — y esa lógica duplicada es donde se mete el error. Una barra de altura cero es más baja que todo, así que obliga al bucle principal a resolver todas las barras restantes.
El ancho. Es i - left - 1, donde left es el índice que está debajo de la barra sacada en la pila, no la barra sacada. Los dos límites son exclusivos: el tramo va estrictamente entre dos barras más bajas. Equivocarte por uno aquí da una respuesta que parece plausible en entradas pequeñas.
Costo: O(n) en tiempo, O(n) en espacio.
Úsalo cuando necesites el rectángulo más grande, el cuadrado más grande en una matriz binaria (ejecuta esto una vez por fila), o cualquier pregunta del tipo «hasta dónde puede extenderse esto antes de que algo lo bloquee».
Patrón 23 — Emparejar paréntesis y corchetes
El uso más simple de una pila, y vale la pena incluirlo porque los detalles son donde se rompe.
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)}");Imprime:
"{[()]}" -> True
"([)]" -> False
"(((" -> False
"" -> True
"a(b[c]d)e" -> TrueLos dos casos que la gente olvida están en esa salida. "(((" falla no porque se haya encontrado un desajuste, sino porque la pila no está vacía al final — cada símbolo de apertura necesita pareja. Y "" es válida, y eso sale de la misma comprobación en vez de necesitar un caso especial.
"([)]" es la razón por la que hace falta una pila. Un contador por cada tipo de símbolo la daría por válida: un (, un ), un [, un ]. El anidamiento es cuestión de orden, y solo una pila registra el orden.
Costo: O(n) en tiempo, O(n) en espacio.
Úsalo cuando algo se anide — paréntesis, etiquetas, análisis de expresiones, historial de deshacer.
Patrón 24 — Una pila que conoce su propio mínimo
Informar el mínimo de todo lo que hay en la pila, en O(1), mientras siguen ocurriendo inserciones y extracciones.
Guardar una sola variable min falla al sacar: cuando se quita el mínimo, hay que volver a buscar el siguiente más pequeño, y eso es O(n).
La solución es dejar de tratar el mínimo como un solo dato sobre toda la pila. Guarda, junto a cada elemento, el mínimo de todo lo que está en ese nivel o debajo.
Un int extra por elemento compra Min() en O(1). Sobrevive a las extracciones porque el mínimo de cada entrada se calculó a partir de lo que estaba debajo, nunca de lo que vino después.
// 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();
}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() = 5Sacar no requiere recalcular nada, y vale la pena decir el motivo con claridad: el mínimo de cada entrada se calculó a partir de lo que estaba debajo, nunca de lo que vino después. Quitar entradas posteriores no puede invalidarlo.
El costo es un int extra por elemento. Mira la secuencia de extracciones en la salida — 5 informa correctamente que su propio mínimo es 5 una vez que todo lo que estaba encima desapareció.
Costo: O(1) para insertar, sacar y consultar el mínimo. O(n) en espacio.
Úsalo cuando necesites un agregado acumulado que sobreviva a las extracciones. La misma forma sirve para el máximo, o para el máximo común divisor.
Patrón 25 — El contenedor que C# no trae
Stack<T> y Queue<T> están los dos, y los dos están bien. No hay un deque respaldado por un arreglo — no existe ArrayDeque.
LinkedList<T> hace el trabajo, y es lo que usó el máximo por ventana deslizante de la parte 2. También asigna un objeto nodo por cada elemento, y con los tamaños de entrada de un concurso esa asignación se nota. Un búfer circular sobre un solo arreglo no, y es lo bastante corto como para escribirlo de memoria.
C# trae Stack<T> y Queue<T> pero ningún deque respaldado por un arreglo. LinkedList<T> llena el hueco y asigna un objeto nodo por elemento; un búfer circular asigna un solo arreglo, y son unas veinte líneas.
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) + "]";
}
}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 allocationToda la idea es % buf.Length. Insertar al frente mueve head hacia atrás y lo envuelve hasta el final del arreglo; nada se desplaza, y los elementos ya no quedan guardados en su orden lógico. ToString recorre head, head+1, … módulo la longitud para recuperarlo.
Fíjate en el + buf.Length dentro de PushFront. En C#, -1 % 8 es -1, no 7 — el operador % conserva el signo del operando izquierdo. Omitir ese término da un índice negativo, y la excepción que lanza queda lejísimos de la línea que la causó.
Costo: O(1) en los dos extremos, un arreglo asignado una sola vez.
Úsalo cuando necesites los dos extremos — máximo por ventana deslizante, BFS 0-1 en la parte 8, o cualquier BFS donde algunas aristas no cuesten nada.
Qué recordar
-
Una pila monótona guarda solo los elementos que todavía esperan una respuesta. Salen ordenados porque a cada uno lo resuelve el primer valor que lo supera.
-
El
whileanidado sigue siendo lineal. Cada índice entra una vez y sale una vez. Dítelo a ti mismo en vez de confiar en la forma del código. -
Usa un centinela en vez de un bucle de vaciado. Una barra de altura cero después del final obliga al bucle principal a resolverlo todo, y elimina la lógica duplicada donde viven los errores.
-
Los anchos del histograma son exclusivos por los dos lados.
i - left - 1, conlefttomado de la pila después de sacar. -
Un paréntesis sin cerrar es una pila no vacía al final. Esa comprobación es la que hace que
"((("falle y""pase, sin casos especiales. -
Una pila con mínimo guarda el mínimo junto a cada elemento, no una sola vez. Sobrevive a las extracciones porque nunca miró más que hacia abajo.
-
C# no tiene deque sobre arreglo, y
-1 % 8es-1. Suma la longitud antes de tomar el módulo, siempre.
La parte 6 son los contenedores propiamente dichos: diccionarios, comparadores personalizados, compresión de coordenadas y PriorityQueue<TElement, TPriority> — que solo llegó en .NET 6, y que mucho material antiguo de concursos en C# todavía esquiva.