Maximiser la hauteur totale des tours uniques : solution gloutonne en Python

Maximiser la hauteur totale de tours uniques (LeetCode 3301) vous donne une hauteur maximale pour chaque tour. Vous devez attribuer à chaque tour une hauteur entière positive qui ne dépasse pas son maximum, toutes les hauteurs étant différentes. Renvoyez la plus grande somme possible, ou -1 si c'est impossible. Une approche gloutonne après tri résout le problème en O(n log n).

Le problème

On vous donne un tableau maximumHeight, où maximumHeight[i] est la hauteur maximale que la tour i peut atteindre. Choisissez height[i] de sorte que :

• 1 <= height[i] <= maximumHeight[i]
• toutes les valeurs height[i] soient distinctes

Renvoyez la somme maximale possible, ou -1 si aucune attribution valide n'existe.

Exemples :

L'idée

Pour rendre le total grand, vous voulez que chaque tour soit aussi haute que possible. Les hauteurs doivent être distinctes, alors réfléchissez à l'ordre : la tour autorisée la plus haute doit recevoir la plus grande valeur, la suivante la plus grande valeur en dessous, et ainsi de suite.

1. Triez les maximums par ordre décroissant.
2. Donnez à la première tour son maximum complet.
3. Pour chaque tour suivante, attribuez min(son maximum, hauteur précédente - 1).
4. Si une hauteur attribuée tombe à 0 ou en dessous, il n'y a pas d'attribution valide, donc renvoyez -1.
5. Additionnez les hauteurs.

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

Trace sur [2,3,4,3] : trié par ordre décroissant, cela donne [4,3,3,2]. Hauteurs : 4, puis min(3, 3) = 3, puis min(3, 2) = 2, puis min(2, 1) = 1. La somme est 10.

Pourquoi le glouton fonctionne

Un argument d'échange le démontre. Supposons qu'une solution optimale attribue une hauteur plus faible à une tour dont le maximum est plus grand qu'à une tour dont le maximum est plus petit. Échanger les deux hauteurs garde les deux dans leurs limites, car la tour avec le plus grand maximum peut prendre n'importe quelle valeur que la plus petite pouvait prendre, et la somme ne change pas. Donc une certaine solution optimale attribue les hauteurs dans le même ordre que les maximums triés.

Une fois l'ordre fixé, chaque tour ne peut pas être plus haute que son propre maximum, ni plus haute que la tour précédente moins un. Prendre exactement cette borne supérieure est optimal : une hauteur plus faible réduirait la somme maintenant, et cela n'aiderait pas les tours suivantes, car leurs bornes supérieures dépendent de cette hauteur, donc l'abaisser ne fait que baisser les leurs aussi.

J'ai aussi vérifié le code contre une recherche par force brute sur toutes les attributions sur 2 000 petits tableaux aléatoires, et les réponses correspondaient.

Complexité

• Temps : O(n log n), dominé par le tri. La boucle est en O(n).
• Espace : O(1) supplémentaire si vous triez sur place, ou O(n) pour une copie triée.

Autre point de vue : le nombre de valeurs

Une autre façon de voir le cas -1 : avec des maximums triés m1 >= m2 >= ... >= mn, une attribution valide n'existe que si le i-ème plus grand maximum est au moins n - i + 1 pour chaque i, puisqu'il vous faut ce nombre de valeurs positives distinctes inférieures ou égales à lui. La boucle vérifie cela au fur et à mesure.

Cas limites

En Java ou en C++, le total peut dépasser 32 bits lorsqu'il y a beaucoup de tours avec de grands maximums, donc utilisez long.

Comment l'expliquer en entretien

1. Reformulez les contraintes, y compris le cas -1.
2. Dites que vous voulez des tours hautes avec des hauteurs distinctes, donc traitez du plus grand maximum vers le bas.
3. Énoncez la règle : chaque hauteur est le minimum de son maximum et de la hauteur précédente moins un.
4. Expliquez pourquoi : échanger les hauteurs entre les tours n'aide pas, et chaque choix est le plus grand possible.
5. Donnez la complexité et la note sur le débordement.
6. Testez avec [2,2,1], un seul élément, et des valeurs toutes égales.

Entraînement associé

Parmi les problèmes similaires de glouton et de tri, on trouve Assign Cookies et Minimum Number of Arrows to Burst Balloons. Consultez notre plan d'étude Blind 75 et notre guide du tuteur IA LeetCode pour savoir comment organiser votre entraînement, ainsi que le guide de l'assistant d'entretien de codage pour les routines de révision.

Expliquez l'argument d'échange à voix haute lorsque vous vous entraînez. Une transcription d'entretien simulé montre si vous avez donné une raison ou seulement le code. Suivez les règles de l'employeur concernant les outils d'IA lors de toute évaluation en direct.