¿Quieres un reto mayor?
Resuelve en 15:00
Importante: Para que se registre el resultado tienes que iniciar sesión.
Máximo rectángulo en histograma
Enunciado
Máximo rectángulo en histograma
Dada una lista de enteros no negativos heights que representa las alturas de las barras de un histograma (cada barra tiene anchura 1), encuentra el área del rectángulo más grande que puede formarse dentro del histograma.
Descripción
El histograma está compuesto por barras adyacentes. Para formar un rectángulo, debes elegir un rango contiguo de barras; la altura del rectángulo está limitada por la barra más baja dentro de ese rango, y su anchura es el número de barras incluidas.
Ejemplos
max_rectangle_histogram([2, 1, 5, 6, 2, 3])
# → 10
# El rectángulo más grande tiene altura 5 y anchura 2 (barras en índices 2 y 3)
max_rectangle_histogram([2, 4])
# → 4
# Se puede tomar solo la barra de altura 4, área = 4
max_rectangle_histogram([0])
# → 0
Restricciones
1 <= len(heights) <= 10^50 <= heights[i] <= 10^4
Pista
Una solución eficiente en O(n) utiliza una pila monotónica para rastrear los índices de barras cuya altura está en orden creciente.
Restriccionesexpand_more
- Dificultad: Difícil
- Completa todos los test cases para obtener los 50 puntos.
- No modificar la línea
exportal final del archivo. - Se recomienda evitar el uso de inteligencia artificial para que realmente tú practiques los ejercicios.
Puedes usar print() para depurar. Los resultados aparecen en la Consola de salida, no en el navegador.