Pila monótona: creciente frente a decreciente
Mantenga una pila creciente o decreciente para responder eficazmente consultas sobre el siguiente elemento mayor y el elemento anterior menor en O(n).
Pila monótona: creciente frente a decreciente es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué es una pila monótona?
Una pila monótona es una pila que mantiene sus elementos ordenados, ya sea siempre en orden creciente desde la base hasta la cima o siempre en orden decreciente. Antes de insertar un elemento nuevo, extraemos todos los elementos que infringen la invariante de monotonicidad. Esta estructura restringida permite resolver en O(n) problemas que, de otro modo, requerirían bucles anidados O(n²).
La idea clave es que cada elemento se inserta y se extrae como máximo una vez, por lo que el número total de operaciones durante todo el recorrido del array es O(n), no O(n²). En el momento en que extraemos un elemento, hemos encontrado la respuesta que estaba esperando.
# Monotonic increasing stack (bottom to top: smallest to largest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] > val:
stack.pop() # maintain increasing invariant
stack.append(val)
print('Increasing stack (left-to-right):', stack) # [1, 1, 2, 6]
# Monotonic decreasing stack (bottom to top: largest to smallest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] < val:
stack.pop() # maintain decreasing invariant
stack.append(val)
print('Decreasing stack (left-to-right):', stack) # [9, 6]Siguiente elemento mayor I
El problema del siguiente elemento mayor consiste en encontrar, para cada elemento, el primer elemento mayor situado a su derecha. Un doble bucle de fuerza bruta O(n²) es demasiado lento. Con una pila monótona decreciente, lo resolvemos en O(n).
Procese los elementos de izquierda a derecha. Antes de insertar el elemento i, extraiga de la pila todos los elementos menores que nums[i]; nums[i] es el siguiente elemento mayor para todos ellos. Después de procesar todos los elementos, los elementos que queden en la pila no tienen ningún elemento mayor a su derecha, por lo que su respuesta es -1.
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # stores indices; stack values are decreasing
for i in range(n):
# Pop elements smaller than nums[i]
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is next greater for idx
stack.append(i)
# Remaining elements in stack have no next greater => keep -1
return result
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums)) # [4, 2, 4, -1, -1]
nums2 = [1, 3, 2, 4]
print(next_greater_element(nums2)) # [3, 4, 4, -1]Elemento siguiente mayor: seguimiento del algoritmo
Veamos paso a paso [2, 1, 2, 4, 3]. Mantenemos una pila decreciente de índices cuyo elemento siguiente mayor aún no se ha encontrado.
- i=0, val=2: la pila está vacía; push 0. Pila: [0]
- i=1, val=1: 1 < nums[0]=2; push 1. Pila: [0,1]
- i=2, val=2: pop 1 (nums[1]=1 < 2), result[1]=2; ahora nums[0]=2 no es < 2; push 2. Pila: [0,2]
- i=3, val=4: pop 2 (result[2]=4), pop 0 (result[0]=4); push 3. Pila: [3]
- i=4, val=3: 3 < nums[3]=4; push 4. Pila: [3,4]
- Al final: stack [3,4] tienen result=-1
def next_greater_trace(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
print(f'i={i} val={nums[i]}: stack={[nums[s] for s in stack]}', end=' => ')
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
print(f'pop {nums[idx]}, NGE={nums[i]};', end=' ')
stack.append(i)
print(f'push {nums[i]}, stack={[nums[s] for s in stack]}')
print('Result:', result)
return result
next_greater_trace([2, 1, 2, 4, 3])Elemento anterior menor
Las pilas monotónicas también permiten responder consultas sobre el elemento anterior menor (PSE): para cada elemento, el elemento más cercano a su izquierda que sea menor. En lugar de hacer pop cuando aparece un elemento mayor, hacemos pop cuando aparece un elemento mayor o igual y registramos la cima de la pila como el PSE antes de hacer push.
La dirección cambia: seguimos procesando de izquierda a derecha, pero en lugar de responder las consultas al hacer pop, respondemos justo antes de hacer push. La cima de la pila en ese momento es el elemento menor más cercano a la izquierda. Si la pila está vacía, no existe ningún elemento menor a la izquierda (la respuesta es -1 o un valor centinela).
def previous_smaller_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # monotonic increasing (values increase bottom to top)
for i in range(n):
# Pop elements >= current (maintain strictly increasing invariant)
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
# Top of stack is previous smaller element (if exists)
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
nums = [4, 5, 2, 10, 8]
print('PSE:', previous_smaller_element(nums)) # [-1, 4, -1, 2, 2]
nums2 = [1, 3, 2, 5, 4]
print('PSE:', previous_smaller_element(nums2)) # [-1, 1, 1, 2, 2]Temperaturas diarias: esperar días más cálidos
El problema de Temperaturas diarias (LeetCode 739): dadas las temperaturas diarias, devuelva un arreglo en el que cada elemento indique cuántos días faltan para encontrar una temperatura más cálida. Este es exactamente el patrón de elemento siguiente mayor, pero en lugar del valor mayor buscamos el número de días (la diferencia entre índices).
Utilice una pila monótona decreciente de índices. Cuando encontramos una temperatura más cálida en el índice i, hacemos pop de todos los índices j de la pila que cumplan temps[j] < temps[i] y establecemos result[j] = i - j. Los índices restantes no tienen ningún día futuro más cálido (result = 0).
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices of unresolved days
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
result[j] = i - j # days until warmer
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps)) # [1, 1, 4, 2, 1, 1, 0, 0]
temps2 = [30, 40, 50, 60]
print(daily_temperatures(temps2)) # [1, 1, 1, 0] (always warmer next day)
temps3 = [30, 60, 90]
print(daily_temperatures(temps3)) # [1, 1, 0]Pila creciente frente a pila decreciente: cuándo usar cada una
Elegir la dirección correcta de la pila es fundamental:
- Pila monótona decreciente (hacer pop cuando current > top): responde consultas sobre el elemento siguiente mayor y el elemento anterior mayor. Se utiliza en daily-temperatures, largest-rectangle y trap-rain-water.
- Pila monótona creciente (hacer pop cuando current < top): responde consultas sobre el elemento siguiente menor y el elemento anterior menor. Se utiliza para encontrar el rango de precios de acciones y el número de personas visibles en una cola.
Recuerde: el elemento que provoca un pop es la respuesta a la consulta del elemento extraído: puede ser el siguiente mayor o el siguiente menor, según el invariante que mantenga.
# Summary: which stack type for which query?
queries = {
'Next Greater Element': 'Decreasing stack (pop when new > top)',
'Next Smaller Element': 'Increasing stack (pop when new < top)',
'Previous Greater Element': 'Decreasing stack (answer = top before push)',
'Previous Smaller Element': 'Increasing stack (answer = top before push)',
}
for query, approach in queries.items():
print(f'{query}:\n => {approach}\n')
# Mnemonic:
# NGE/PGE => decreasing stack (we pop smaller elements, finding their next/prev larger)
# NSE/PSE => increasing stack (we pop larger elements, finding their next/prev smaller)Elemento siguiente mayor circular
Elemento siguiente mayor II (LeetCode 503): dado un arreglo circular (con vuelta al inicio), encuentre el elemento siguiente mayor. El truco consiste en procesar el arreglo dos veces duplicando los índices: recorra de 0 a 2n-1 y utilice index % n para dar la vuelta al arreglo. Haga push únicamente de los índices de 0 a n-1 (en la primera pasada) para no contar los elementos dos veces.
Como alternativa, procese el arreglo en la segunda pasada sin hacer push de índices nuevos; haga únicamente pop. Esto gestiona correctamente la búsqueda circular hacia delante sin duplicar realmente el arreglo y mantiene el espacio en O(n).
def next_greater_element_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n:
stack.append(i) # only push real indices (0..n-1)
return result
print(next_greater_element_circular([1, 2, 1])) # [2, -1, 2]
print(next_greater_element_circular([1, 2, 3, 4, 3])) # [2, 3, 4, -1, 4]
print(next_greater_element_circular([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Problema del Stock Span
El problema de Stock Span: dados los precios diarios de una acción, calcule el rango de cada día: el número de días consecutivos anteriores cuyo precio es menor o igual que el precio de hoy. En realidad, es el problema del elemento anterior mayor: el rango es la distancia desde hoy hasta el día más cercano con un precio estrictamente mayor.
Utilice una pila monótona decreciente. Al procesar el día i, haga pop de todos los días cuyo precio sea ≤ el actual. El rango es i - stack[-1] si la pila no está vacía, o i + 1 si está vacía (el precio es el máximo hasta ese momento). Después, haga push de i.
def stock_span(prices):
spans = []
stack = [] # indices of prices forming decreasing sequence
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
span = i - stack[-1] if stack else i + 1
spans.append(span)
stack.append(i)
return spans
prices = [100, 80, 60, 70, 60, 75, 85]
print('Prices:', prices)
print('Spans: ', stock_span(prices)) # [1, 1, 1, 2, 1, 4, 6]
# Verification for day 5 (price=75): prev higher is day 1 (80), span = 5-1 = 4
# Day 6 (price=85): prev higher is day 0 (100), span = 6-0 = 6Pila monótona para personas visibles en una cola
El problema del número de personas visibles en una cola: varias personas están de pie en una cola y cada una tiene una altura. La persona i puede ver a la persona j (j > i) si todas las personas que están entre ellas son más bajas que ambas. Este problema utiliza una pila monótona decreciente.
Procese de derecha a izquierda. Mantenga una pila decreciente de alturas. Para cada persona, cuente a cuántas personas puede ver: haga pop de todas las personas más bajas (son visibles, pero dejan de bloquear la vista), y sume 1 si la pila no está vacía después de hacerlo (la primera persona más alta también es visible). El resultado es O(n) en total, porque cada persona se inserta y se extrae como máximo una vez.
def visible_people(heights):
n = len(heights)
result = [0] * n
stack = [] # decreasing monotonic stack (heights)
for i in range(n - 1, -1, -1): # right to left
count = 0
while stack and stack[-1] < heights[i]:
stack.pop()
count += 1 # can see this shorter person
if stack:
count += 1 # can see the first person >= heights[i]
result[i] = count
stack.append(heights[i])
return result
heights = [10, 6, 8, 5, 11, 9]
print('Heights:', heights)
print('Visible:', visible_people(heights)) # [3, 1, 2, 1, 1, 0]Garantía O(n): por qué cada elemento se inserta y se extrae como máximo una vez
La garantía de tiempo O(n) de los algoritmos con pilas monótonas se debe a un sencillo argumento de amortización: cada elemento se inserta en la pila exactamente una vez y se extrae como máximo una vez. Ningún elemento puede insertarse o extraerse más de una vez. Por lo tanto, el número total de operaciones push + pop en todo el bucle es como máximo 2n, lo que produce un trabajo total O(n), aunque el bucle while anidado parezca sugerir O(n²).
Es importante saber explicar este análisis amortizado en las entrevistas. El bucle while no se ejecuta n veces en cada iteración: solo se ejecuta las veces necesarias para extraer los elementos que estaban esperando, y esos elementos desaparecen para siempre después de ser extraídos.
def next_greater_instrumented(nums):
result = [-1] * len(nums)
stack = []
pushes = pops = 0
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
pops += 1
stack.append(i)
pushes += 1
print(f'n={len(nums)}, pushes={pushes}, pops={pops}')
print(f'Total operations = {pushes + pops} <= 2n = {2*len(nums)}')
return result
import random
nums = random.sample(range(1000), 100)
next_greater_instrumented(nums)
# Confirm: total operations always <= 2nCómo reconocer problemas de pilas monótonas
Es probable que un problema necesite una pila monótona si solicita el elemento mayor o menor más cercano, el rango de precios, los elementos visibles en una fila o áreas basadas en histogramas. Busque estas palabras clave y patrones: cada elemento necesita la respuesta del elemento relevante más cercano en una dirección (izquierda o derecha).
Si una solución por fuerza bruta recorre hacia la izquierda o hacia la derecha desde cada elemento (O(n²)), sustituya ese recorrido por una pila monótona. La pila «recuerda» las respuestas candidatas, descarta las irrelevantes y extrae la respuesta correcta justo en el momento en que se necesita.
# Monotonic stack problem recognition guide
patterns = [
('Next/previous greater element', 'Decreasing stack; answer found on pop'),
('Next/previous smaller element', 'Increasing stack; answer found on pop'),
('Days until warmer/colder', 'Stack of indices; answer = i - j'),
('Stock span', 'Decreasing stack; span = i - prev larger idx'),
('Largest rectangle in histogram', 'Increasing stack; area computed on pop'),
('Trapping rain water', 'Decreasing stack or two-pointer'),
('Sliding window maximum', 'Decreasing deque of indices'),
]
print('Monotonic Stack / Deque Pattern Guide:')
print('='*60)
for problem, approach in patterns:
print(f'Problem: {problem}')
print(f' Approach: {approach}')
print()Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que una pila monótona mantiene un orden creciente o decreciente haciendo pop de los elementos que infringen el invariante antes de hacer push, que una pila decreciente responde sobre el elemento siguiente o anterior mayor, mientras que una pila creciente responde sobre el elemento siguiente o anterior menor y que cada elemento se inserta y se extrae como máximo una vez, lo que produce un tiempo total O(n), no O(n²). A continuación, aplicaremos la pila monótona para encontrar el rectángulo más grande en un histograma.
Preguntas frecuentes
¿La lección «Pila monótona: creciente frente a decreciente» es gratis?
Sí — el texto completo de «Pila monótona: creciente frente a decreciente» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Pila monótona: creciente frente a decreciente»?
Mantenga una pila creciente o decreciente para responder eficazmente consultas sobre el siguiente elemento mayor y el elemento anterior menor en O(n). Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Pila monótona: creciente frente a decreciente»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Pila monótona: creciente frente a decreciente
- Rectángulo más grande en un histograma
- Máximo de ventana deslizante con deque monótona
- Trapping Rain Water: pila y dos punteros