Maximizar la altura total de torres únicas (LeetCode 3301) te da una altura máxima para cada torre. Debes asignar a cada torre una altura entera positiva que no supere su máximo, con todas las alturas diferentes. Devuelve la mayor suma posible, o -1 si no se puede. Un enfoque greedy tras ordenar lo resuelve en O(n log n).
El problema
Se te da un array maximumHeight, donde maximumHeight[i] es la torre más alta que puede ser la torre i. Elige height[i] de modo que:
- 1 <= height[i] <= maximumHeight[i]
- todos los valores de height[i] sean distintos
Devuelve la suma máxima posible, o -1 si no existe ninguna asignación válida.
Ejemplos:
| Entrada | Salida | Por qué |
|---|---|---|
| [2,3,4,3] | 10 | Alturas 4, 3, 2, 1 |
| [15,10] | 25 | Alturas 15 y 10 |
| [2,2,1] | -1 | Solo hay disponibles las alturas 1 y 2 para tres torres |
La idea
Para que el total sea grande, quieres que cada torre sea lo más alta posible. Las alturas deben ser distintas, así que piensa en el orden: la torre con el máximo más alto debería recibir el valor más grande, la siguiente el valor más grande por debajo de ese, y así sucesivamente.
- Ordena los máximos en orden descendente.
- Dale a la primera torre su máximo completo.
- Para cada torre siguiente, asigna min(su máximo, altura anterior - 1).
- Si una altura asignada baja a 0 o menos, no hay asignación válida, así que devuelve -1.
- Suma las alturas.
def maximum_total_sum(maximum_height):
total = 0
limit = float("inf")
for m in sorted(maximum_height, reverse=True):
h = min(m, limit - 1)
if h <= 0:
return -1
total += h
limit = h
return total
Traza sobre [2,3,4,3]: ordenado de forma descendente es [4,3,3,2]. Alturas: 4, luego min(3, 3) = 3, luego min(3, 2) = 2, luego min(2, 1) = 1. La suma es 10.
Por qué funciona el greedy
Lo demuestra un argumento de intercambio. Supón que una solución óptima da una altura menor a una torre con un máximo mayor que a otra con un máximo menor. Intercambiar las dos alturas mantiene ambas dentro de sus límites, porque la torre con el máximo mayor puede tomar cualquier valor que pudiera tomar la menor, y la suma no cambia. Así que alguna solución óptima asigna las alturas en el mismo orden que los máximos ordenados.
Una vez fijado el orden, cada torre no puede ser más alta que su propio máximo, ni más alta que uno menos que la torre anterior. Tomar exactamente esa cota superior es lo mejor: una altura menor reduciría la suma ahora, y no ayudaría a las torres posteriores, porque sus cotas superiores dependen de esta altura, así que bajarla solo baja también las suyas.
También comprobé el código contra una búsqueda por fuerza bruta sobre todas las asignaciones en 2.000 arrays pequeños aleatorios, y las respuestas coincidían.
Complejidad
- Tiempo: O(n log n), dominado por el ordenamiento. El bucle es O(n).
- Espacio: O(1) extra si ordenas in situ, u O(n) para una copia ordenada.
Otra perspectiva: recuento de valores
Otra forma de ver el caso -1: con los máximos ordenados m1 >= m2 >= ... >= mn, existe una asignación válida solo si el i-ésimo máximo más grande es al menos n - i + 1 para cada i, ya que necesitas esa cantidad de valores positivos distintos iguales o menores que él. El bucle comprueba esto a medida que avanza.
Casos límite
| Entrada | Resultado |
|---|---|
| [1] | 1 |
| [1,1] | -1 |
| [5,5,5] | 12 (5, 4, 3) |
| [10] | 10 |
| Ya distintos y descendentes | La suma del array |
| Valores grandes, array largo | Usa un tipo entero de 64 bits en lenguajes que desbordan |
En Java o C++, el total puede superar los 32 bits cuando hay muchas torres con máximos grandes, así que usa long.
Cómo explicarlo en una entrevista
- Reformula las restricciones, incluido el caso -1.
- Di que quieres torres altas con alturas distintas, así que procesa desde el máximo más grande hacia abajo.
- Enuncia la regla: cada altura es el mínimo entre su máximo y uno menos que la altura anterior.
- Explica por qué: intercambiar alturas entre torres no ayuda, y cada elección es la mayor posible.
- Da la complejidad y la nota sobre el desbordamiento.
- Prueba con [2,2,1], un solo elemento y todos los valores iguales.
Práctica relacionada
Entre los problemas similares de greedy y ordenamiento están Assign Cookies y Minimum Number of Arrows to Burst Balloons. Consulta nuestro plan de estudio Blind 75 y la guía del tutor de LeetCode con IA para saber cómo organizar la práctica, y la guía del asistente para entrevistas de programación para rutinas de repaso.
Explica el argumento de intercambio en voz alta cuando practiques. Una transcripción de entrevista simulada muestra si diste una razón o solo el código. Sigue las normas del empleador sobre herramientas de IA en cualquier evaluación en vivo.
Practica entrevistas de programación con YesToTheOffer
Realiza una entrevista de programación simulada, explica tu razonamiento en voz alta y revisa tu transcripción después. 30 minutos gratis, sin suscripción.
