Rectángulo más grande en un histograma
Use una pila monótona para seguir los límites izquierdos y calcular, en una sola pasada, el rectángulo de área máxima que cabe en un histograma.
Rectángulo más grande en un histograma es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 2 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 DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
Problema: rectángulo más grande en un histograma
El problema del rectángulo más grande en un histograma (LeetCode 84) proporciona un arreglo de enteros no negativos que representan las alturas de las barras de un histograma, donde cada barra tiene un ancho de 1. Encuentre el área del rectángulo más grande que se pueda formar dentro del histograma. El rectángulo debe abarcar barras contiguas y su altura está limitada por la barra más baja que cubre.
Un enfoque por fuerza bruta: para cada par (i, j), calcule la altura mínima en [i, j] y multiplíquela por (j - i + 1). Esto es O(n³), u O(n²) si se calculan previamente los mínimos; resulta demasiado lento. La solución con una pila monótona se ejecuta en O(n).
# Example: heights = [2, 1, 5, 6, 2, 3]
# Rectangles:
# width=1, height=6 at index 3 => area=6
# width=2, height=5 at indices 2-3 => area=10 (maximum!)
# width=6, height=1 across all => area=6
# width=3, height=2 at indices 2-4 => area=6
heights = [2, 1, 5, 6, 2, 3]
print('Heights:', heights)
print('Expected max area: 10 (bars of height 5 and 6, width 2)')
# Brute force for small inputs:
def brute_force(heights):
n = len(heights)
max_area = 0
for i in range(n):
min_h = heights[i]
for j in range(i, n):
min_h = min(min_h, heights[j])
max_area = max(max_area, min_h * (j - i + 1))
return max_area
print('Brute force answer:', brute_force(heights)) # 10Idea clave: ¿qué limita el rectángulo de cada barra?
Para cada barra i de altura h, el rectángulo más grande en el que puede ser la altura mínima se extiende hacia la izquierda hasta la primera barra más baja que h y hacia la derecha hasta la primera barra más baja que h. El ancho es right_boundary - left_boundary - 1 y el área es h × width.
Esto reformula el problema: para cada barra, encuentre su elemento anterior menor (PSE) y su elemento siguiente menor (NSE). Eso es exactamente lo que calcula una pila monótona creciente. En el momento en que hacemos pop de la barra i (porque se ha encontrado una barra más baja), la barra actual es su NSE y la cima de la pila después del pop es su PSE.
heights = [2, 1, 5, 6, 2, 3]
n = len(heights)
# Find PSE and NSE for each bar
pse = [-1] * n # index of previous smaller element
nse = [n] * n # index of next smaller element (default: beyond array)
# PSE
stack = []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
# NSE
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
max_area = 0
for i in range(n):
width = nse[i] - pse[i] - 1
area = heights[i] * width
print(f'Bar {i} (h={heights[i]}): PSE={pse[i]}, NSE={nse[i]}, width={width}, area={area}')
max_area = max(max_area, area)
print('Max area:', max_area)Solución en una pasada con una pila monótona
El enfoque en dos pasadas anterior funciona, pero puede combinarse en una sola pasada. Procese las barras de izquierda a derecha con una pila monótona creciente. Cuando la barra i sea más baja que la cima de la pila, haga pop de la cima: la altura de la barra extraída es la altura de un rectángulo, su límite derecho es i y su límite izquierdo es la nueva cima de stack + 1.
Un truco habitual consiste en añadir un 0 centinela al final de heights. Esto garantiza que todas las barras se extraigan de la pila al final, incluso si ninguna barra más baja aparece de forma natural. Sin el centinela, necesitaría una fase de limpieza después del bucle para los elementos restantes de la pila.
def largest_rectangle(heights):
stack = [] # monotonic increasing: indices of bars
max_area = 0
heights = heights + [0] # sentinel: forces all bars to be popped
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()] # height of the rectangle
width = i if not stack else i - stack[-1] - 1 # left boundary
max_area = max(max_area, height * width)
stack.append(i)
return max_area
print(largest_rectangle([2, 1, 5, 6, 2, 3])) # 10
print(largest_rectangle([2, 4])) # 4
print(largest_rectangle([1, 1])) # 2
print(largest_rectangle([0, 9])) # 9
print(largest_rectangle([6, 7, 5, 2, 4, 5, 9, 3])) # 16Seguimiento del algoritmo en una pasada
Veamos paso a paso [2, 1, 5, 6, 2, 3, 0] (con centinela):
- i=0, h=2: push 0. Pila: [0]
- i=1, h=1: pop 0 (h=2, width=1, area=2). La pila queda vacía; push 1. Pila: [1]
- i=2, h=5: 5>1; push 2. Pila: [1,2]
- i=3, h=6: 6>5; push 3. Pila: [1,2,3]
- i=4, h=2: pop 3 (h=6,width=4-2-1=1,area=6), pop 2 (h=5,width=4-1-1=2,area=10★); 2>1, detenerse. Push 4. Pila: [1,4]
- i=5, h=3: 3>2; push 5. Pila: [1,4,5]
- i=6, centinela h=0: hacer pop de todos y calcular las áreas...
def largest_rectangle_trace(heights):
stack = []
max_area = 0
hs = heights + [0]
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = hs[top] * w
print(f' Pop bar {top} (h={hs[top]}): width={w}, area={area}', end='')
if area > max_area:
max_area = area
print(' *** NEW MAX ***', end='')
print()
print(f'i={i} h={h}: push {i}, stack={[hs[s] for s in stack + [i]]}')
stack.append(i)
print(f'Max area: {max_area}')
return max_area
largest_rectangle_trace([2, 1, 5, 6, 2, 3])Cálculo del ancho: ¿por qué i - stack[-1] - 1?
Cuando hacemos pop de la barra j de la pila, sabemos lo siguiente: el límite derecho del rectángulo de j es i (la primera barra a la derecha que es más baja que j). El límite izquierdo es la barra que queda inmediatamente debajo de j en la pila después del pop; llamémosla k. Por lo tanto, el ancho es i - k - 1 (las barras desde k+1 hasta i-1, ambas inclusive).
Si la pila está vacía después del pop, el rectángulo de j se extiende hasta el borde izquierdo (índice 0). El ancho es simplemente i (los índices de 0 a i-1, cuyas alturas son todas al menos tan grandes como heights[j]). Este es el caso especial width = i if not stack else i - stack[-1] - 1.
# Illustrating left/right boundary logic
heights = [1, 3, 5, 2]
# After processing with stack:
# When we pop bar 2 (h=5) at i=3 (h=2):
# stack after pop = [0, 1] => left boundary = 1+1=2, right=3-1=2 => width=1
# When we pop bar 1 (h=3) at i=3 (h=2):
# stack after pop = [0] => left boundary = 0+1=1, right=3-1=2 => width=2
# etc.
def compute_boundaries(heights):
hs = heights + [0]
stack = []
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
if stack:
left = stack[-1] + 1
width = i - stack[-1] - 1
else:
left = 0
width = i
print(f'Bar {top} (h={hs[top]}): extends from {left} to {i-1}, width={width}')
stack.append(i)
compute_boundaries([2, 1, 5, 6, 2, 3])Rectángulo máximo en una matriz binaria
Rectángulo máximo (LeetCode 85) extiende el problema del histograma a una matriz binaria bidimensional. Para cada fila, calcule la altura de los 1 consecutivos situados encima de cada celda. Esto crea un histograma para esa fila. Aplique el algoritmo del rectángulo más grande en un histograma al histograma de cada fila. El máximo general entre todas las filas es la respuesta.
Esto reduce un problema bidimensional a n problemas unidimensionales repetidos de histogramas. La complejidad temporal es O(m × n) para una matriz de m filas y n columnas: una pasada por el histograma de cada fila, con O(n) en cada pasada.
def maximal_rectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
max_area = 0
def hist_max_area(h):
stack, area = [], 0
for i, hh in enumerate(h + [0]):
while stack and h[stack[-1]] > hh:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = max(area, h[top] * w)
stack.append(i)
return area
for row in matrix:
for j in range(n):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
max_area = max(max_area, hist_max_area(heights[:]))
return max_area
matrix = [['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1'],
['1','0','0','1','0']]
print(maximal_rectangle(matrix)) # 6Casos límite en problemas de histogramas
Casos límite importantes que debe gestionar:
- Todas las barras tienen la misma altura: todo el arreglo forma un solo rectángulo; respuesta = n × height
- Orden estrictamente creciente: no se hace pop hasta llegar al centinela; el área de la última barra es el máximo
- Una sola barra: respuesta = height[0]
- Barras con altura 0: actúan como centinelas naturales y dividen el histograma en segmentos independientes
El centinela (añadir 0) al final gestiona el caso estrictamente creciente al forzar la extracción de todas las barras restantes al final. Sin él, necesitaría un bucle de limpieza independiente después de la iteración principal.
def largest_rectangle(heights):
stack = []
max_area = 0
heights = heights + [0]
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, heights[top] * w)
stack.append(i)
return max_area
# Edge cases
print(largest_rectangle([5, 5, 5, 5])) # 20 (all same)
print(largest_rectangle([1, 2, 3, 4, 5])) # 9 (increasing: 3*3)
print(largest_rectangle([5, 4, 3, 2, 1])) # 9 (decreasing: 3*3)
print(largest_rectangle([5])) # 5 (single bar)
print(largest_rectangle([0, 0, 0])) # 0 (all zero)
print(largest_rectangle([3, 0, 3])) # 3 (zero splits)Alternativa de divide y vencerás
El problema del histograma también puede resolverse con divide y vencerás: divida en la barra de altura mínima, resuelva cada mitad de forma recursiva y compare con el rectángulo que abarca todo el ancho utilizando la altura mínima. Esto produce O(n log n) en promedio, pero O(n²) en el peor caso para entradas ordenadas.
El enfoque de la pila monótona es estrictamente superior, con O(n) en el peor caso. Sin embargo, comprender el enfoque de divide y vencerás profundiza la intuición sobre el problema y explica por qué la barra de altura mínima de cualquier segmento siempre es el factor limitante de los rectángulos de ancho completo.
def largest_rectangle_dc(heights, lo=0, hi=None):
if hi is None:
hi = len(heights) - 1
if lo > hi:
return 0
# Find the index of the minimum height in [lo, hi]
min_idx = lo
for i in range(lo, hi + 1):
if heights[i] < heights[min_idx]:
min_idx = i
# Three options:
# 1. Max rect entirely in left half
# 2. Max rect entirely in right half
# 3. Max rect spanning entire [lo, hi] with height = min
full_width_area = heights[min_idx] * (hi - lo + 1)
left_area = largest_rectangle_dc(heights, lo, min_idx - 1)
right_area = largest_rectangle_dc(heights, min_idx + 1, hi)
return max(full_width_area, left_area, right_area)
print(largest_rectangle_dc([2, 1, 5, 6, 2, 3])) # 10Patrón de histograma: conteo de subarreglos
Un problema relacionado que utiliza la misma técnica de pila: cuente el número de subarreglos de un histograma cuyo elemento mínimo sea igual a un objetivo determinado. Esto se resuelve calculando el PSE y el NSE de cada barra y utilizando la fórmula (i - pse[i]) × (nse[i] - i), que cuenta los subhistogramas en los que la barra i es el mínimo.
Esta técnica de «cantidad izquierda × cantidad derecha» aparece en varios problemas de LeetCode: suma de mínimos de subarreglos (907), conteo de subcadenas con todos sus caracteres únicos y problemas que utilizan la técnica de contribuciones. La pila monótona calcula el PSE y el NSE en O(n), lo que permite calcular la contribución de cada elemento en O(1).
def sum_of_subarray_minimums(arr):
n = len(arr)
pse = [-1] * n # previous strictly smaller element
nse = [n] * n # next smaller or equal element
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
MOD = 10**9 + 7
total = 0
for i in range(n):
left_count = i - pse[i] # subarrays where i is leftmost min
right_count = nse[i] - i # subarrays where i is the min
total += arr[i] * left_count * right_count
return total % MOD
print(sum_of_subarray_minimums([3, 1, 2, 4])) # 17
print(sum_of_subarray_minimums([11, 81, 94, 43, 3])) # 444Consejos prácticos para entrevistas
Cuando se encuentre con un problema de histogramas en una entrevista, siga esta lista de comprobación:
- Aclare: ¿las alturas pueden ser 0? ¿Cuál es la salida: el área, los índices o el recuento?
- Empiece con la fuerza bruta e indique una complejidad O(n²) u O(n³)
- Mencione que la contribución de cada barra depende de su extensión hacia la izquierda y la derecha hasta la barra más cercana de menor altura
- Introduzca PSE/NSE → pila monótona → solución O(n)
- Gestione el truco del centinela (añada 0) para simplificar el código
- Trace un ejemplo pequeño en la pizarra
Una pregunta de seguimiento habitual es extenderlo a 2D (rectángulo máximo). Demuestre que puede reducirlo a n problemas de histogramas, cada uno en O(n), para obtener O(m×n) en total.
# Final clean solution for interview
def largest_rectangle_in_histogram(heights):
stack = []
max_area = 0
for i, h in enumerate(heights + [0]): # sentinel forces final pops
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
# Verify all test cases from earlier
test_cases = [
([2, 1, 5, 6, 2, 3], 10),
([6, 7, 5, 2, 4, 5, 9, 3], 16),
([1], 1),
([2, 0, 2], 2),
([], 0),
]
for heights, expected in test_cases:
if not heights:
result = 0
else:
result = largest_rectangle_in_histogram(heights)
status = 'PASS' if result == expected else 'FAIL'
print(f'{status}: {heights} => {result} (expected {expected})')Suma de rangos de subarreglos y variantes similares
La técnica PSE/NSE se generaliza a varios problemas de LeetCode. Suma de rangos de subarreglos (2104) pide calcular la suma de (máximo - mínimo) en todos los subarreglos. Esto equivale a (suma de los máximos de los subarreglos) menos (suma de los mínimos de los subarreglos), y cada suma se calcula con una pila monótona en O(n). Número de personas visibles en una cola (1944) utiliza una pila decreciente en la que cada extracción cuenta a una persona visible. Reconocer esta familia de problemas consiste en identificar la frase «para cada elemento, ¿hasta dónde puede dominar?»: la respuesta siempre es PSE/NSE con una pila monótona.
def sum_subarray_ranges(nums):
n = len(nums)
# Sum of subarray max - sum of subarray min
def contrib(arr, is_max):
# Count contribution of each element as max (or min)
n = len(arr)
left = [0]*n; right = [0]*n
stack = []
for i in range(n):
while stack and (arr[stack[-1]] < arr[i] if is_max else arr[stack[-1]] > arr[i]):
stack.pop()
left[i] = i - (stack[-1] if stack else -1)
stack.append(i)
stack = []
for i in range(n-1, -1, -1):
while stack and (arr[stack[-1]] <= arr[i] if is_max else arr[stack[-1]] >= arr[i]):
stack.pop()
right[i] = (stack[-1] if stack else n) - i
stack.append(i)
return sum(arr[i] * left[i] * right[i] for i in range(n))
return contrib(nums, True) - contrib(nums, False)
print(sum_subarray_ranges([1, 2, 3])) # 4
print(sum_subarray_ranges([1, 3, 3])) # 4
print(sum_subarray_ranges([4, -2, -3, 4, 1])) # 59Comprobació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 aprendió que para cada barra, los límites de su rectángulo contenedor más grande los define la barra más cercana de menor altura a cada lado (PSE y NSE), que una pila monótona creciente calcula todos los límites PSE/NSE en un único recorrido O(n), encontrando ambos al extraer las barras, y que añadir un 0 como centinela garantiza que todas las barras se extraigan de la pila y simplifica el código a un único bucle. A continuación, aplicaremos el deque monótono para resolver el máximo en una ventana deslizante en O(n).
Preguntas frecuentes
¿La lección «Rectángulo más grande en un histograma» es gratis?
Sí — el texto completo de «Rectángulo más grande en un histograma» 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 DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Rectángulo más grande en un histograma»?
Use una pila monótona para seguir los límites izquierdos y calcular, en una sola pasada, el rectángulo de área máxima que cabe en un histograma. Practicas DSA 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 DSA Interview Prep?
No se requiere experiencia previa. DSA 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 2 de 4.
¿Cuánto tiempo toma la lección «Rectángulo más grande en un histograma»?
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 DSA Interview Prep?
Sí. Cada lección de DSA 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