Patrón de pila monótona

Una pila monótona es una pila que mantiene un invariante ordenado entre sus elementos. Una pila monótona creciente tiene elementos que aumentan de abajo arriba; una pila monótona decreciente tiene elementos que disminuyen de abajo arriba. Cuando un elemento nuevo infringe el invariante, se extraen elementos hasta restaurarlo y, después, se inserta el elemento nuevo.

Este mecanismo sencillo permite responder en O(n) a consultas sobre el «elemento mayor más cercano» y el «elemento menor más cercano», que ingenuamente requerirían bucles anidados de O(n²).

Para cada elemento, encuentre el primer elemento estrictamente mayor a su derecha. Una solución de fuerza bruta O(n²) recorre hacia la derecha desde cada posición. El enfoque de la pila monótona consiste en mantener una pila decreciente de índices. Cuando se encuentra un elemento mayor, se extraen todos los índices de elementos menores: el «siguiente elemento mayor» de estos es el elemento actual. Los índices restantes no tienen un siguiente elemento mayor (su respuesta es -1).

LeetCode 503, «Next Greater Element II»: el mismo problema, pero el array se considera circular. Después de llegar al final, vuelva al principio y continúe comprobando. El truco consiste en recorrer el array dos veces (índices de 0 a 2n-1) y utilizar i % n para indexar el array original. Introduzca únicamente índices del rango [0, n-1] en la pila para evitar procesarlos dos veces.

Repaso de LeetCode 739: para cada día, ¿cuántos días deben transcurrir hasta encontrar una temperatura más cálida? La pila monótona contiene los índices de los días cuyas temperaturas están en orden decreciente. Cuando se encuentra un día más cálido i, se extraen de la pila todos los índices j de días más fríos y se registra result[j] = i - j. Los días que quedan en la pila nunca encontraron un día más cálido, por lo que su resultado permanece en 0.

La consulta del «elemento menor anterior» pregunta: para cada elemento, ¿cuál es el valor menor más cercano a su izquierda? Utilice una pila monótona creciente y procese los elementos de izquierda a derecha. Antes de insertar el índice i, la cima de la pila es el elemento menor anterior, porque todos los elementos mayores que nums[i] ya se eliminaron durante inserciones anteriores, cuando elementos mayores provocaron su extracción.

LeetCode 84, «Largest Rectangle in Histogram»: utilice una pila monótona creciente de índices. Para cada barra, extraiga todas las barras más altas que la actual. Para cada barra extraída h, su límite derecho es el índice actual i y su límite izquierdo es la nueva cima de la pila + 1 (o 0 si la pila está vacía). Área = h × (right - left). Añada un centinela de altura 0 para forzar la extracción de todas las barras restantes al final.

LeetCode 85, «Maximal Rectangle», extiende el problema del histograma a una matriz binaria 2D. Para cada fila, calcule las alturas acumuladas de las barras: si matrix[row][col] == '1', la altura es el número de 1 consecutivos situados encima de esta celda e incluyéndola. Después, aplique el algoritmo del «rectángulo más grande en un histograma» al array de alturas de cada fila. Tiempo: O(m × n) para una matriz de m×n.

LeetCode 42, «Trapping Rain Water», con una pila: mantenga una pila decreciente de índices. Cuando se encuentra una barra más alta, se forma un valle. Extraiga el fondo del valle; calcule el ancho del agua como (current_index - stack_top - 1) y la altura como (min(current_bar, new_stack_top_bar) - valley_height). Sume todas las contribuciones. Tiempo: O(n), espacio: O(n).

Estas son señales de que una pila monótona es la herramienta adecuada: el problema pide el siguiente o anterior elemento mayor o menor, la respuesta para cada elemento depende de elementos situados en una dirección concreta, o una solución ingenua de O(n²) implica recorrer hacia la izquierda o la derecha para cada elemento. La pila almacena candidatos que podrían ser respuestas para elementos futuros y los descarta en cuanto aparece un candidato mejor.

Decida siempre de antemano: creciente (para el siguiente o anterior elemento menor) o decreciente (para el siguiente o anterior elemento mayor), y desde qué dirección procesará los elementos.

Al principio, los algoritmos de pila monótona parecen ser O(n log n) u O(n²) debido al bucle while dentro del bucle for. Sin embargo, cada elemento se inserta como máximo una vez y se extrae como máximo una vez. El número total de operaciones de inserción es n y el número total de operaciones de extracción también es como máximo n. Por tanto, en todas las iteraciones el trabajo total es de 2n operaciones: O(n) amortizado, no O(n²).

Elija la dirección de la pila según la consulta. Para el siguiente elemento mayor, utilice una pila decreciente: extraiga elementos cuando el elemento actual sea mayor. Para el siguiente elemento menor, utilice una pila creciente: extraiga elementos cuando el elemento actual sea menor. Para el rectángulo más grande, utilice una pila creciente y extraiga elementos cuando aparezca una barra más baja. Para el máximo de una ventana deslizante, utilice una deque decreciente y elimine elementos por ambos extremos.

Escribir el invariante en un comentario antes de programar aclara la lógica y agiliza la depuración.

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección ha aprendido: una pila monótona mantiene un invariante ordenado extrayendo los elementos que lo infringen antes de insertar el elemento nuevo, las pilas decrecientes responden a consultas sobre el siguiente elemento mayor; las pilas crecientes responden a consultas sobre el siguiente elemento menor, y el tiempo total es O(n) amortizado porque cada elemento se inserta y se extrae como máximo una vez. A continuación implementaremos colas utilizando pilas y pilas utilizando colas.