Maximaliseer de totale hoogte van unieke torens: hebzuchtige oplossing in Python

Maximaliseer de totale hoogte van unieke torens (LeetCode 3301) geeft je een maximale hoogte voor elke toren. Je moet elke toren een positief geheel getal als hoogte geven dat niet groter is dan het maximum, waarbij alle hoogtes verschillend zijn. Geef de grootst mogelijke totale hoogte terug, of -1 als het niet kan. Een greedy-aanpak na sorteren lost het op in O(n log n).

Het probleem

Je krijgt een array maximumHeight, waarbij maximumHeight[i] de hoogste toren is die i mag zijn. Kies height[i] zodat:

• 1 <= height[i] <= maximumHeight[i]
• alle height[i]-waarden verschillend zijn

Geef de maximaal mogelijke som terug, of -1 als er geen geldige toewijzing bestaat.

Voorbeelden:

Het idee

Om het totaal groot te maken, wil je elke toren zo hoog mogelijk. Hoogtes moeten verschillend zijn, dus denk aan de volgorde: de toren met het grootste toegestane maximum krijgt de grootste waarde, de volgende de grootste waarde daaronder, enzovoort.

1. Sorteer de maxima in aflopende volgorde.
2. Geef de eerste toren zijn volledige maximum.
3. Wijs voor elke volgende toren min(zijn maximum, vorige hoogte - 1) toe.
4. Als een toegewezen hoogte 0 of lager wordt, is er geen geldige toewijzing, dus geef -1 terug.
5. Tel de hoogtes op.

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 op [2,3,4,3]: aflopend gesorteerd is [4,3,3,2]. Hoogtes: 4, dan min(3, 3) = 3, dan min(3, 2) = 2, dan min(2, 1) = 1. De som is 10.

Waarom de greedy-aanpak werkt

Een uitwisselingsargument toont dit aan. Stel dat een optimale oplossing een lagere hoogte geeft aan een toren met een groter maximum dan aan een met een kleiner maximum. Het omwisselen van de twee hoogtes houdt beide binnen hun grenzen, omdat de toren met het grotere maximum elke waarde kan aannemen die de kleinere ook kon, en de som verandert niet. Dus een of andere optimale oplossing wijst hoogtes toe in dezelfde volgorde als de gesorteerde maxima.

Zodra de volgorde vastligt, kan elke toren niet hoger zijn dan zijn eigen maximum, en niet hoger dan één minder dan de toren ervoor. Precies die bovengrens nemen is het beste: een lagere hoogte zou de som nu verkleinen, en het zou de latere torens niet helpen, omdat hun bovengrenzen van deze hoogte afhangen, dus het verlagen ervan verlaagt ook die van hen.

Ik heb de code ook gecontroleerd tegen een brute-force zoektocht over alle toewijzingen op 2.000 willekeurige kleine arrays, en de antwoorden kwamen overeen.

Complexiteit

• Tijd: O(n log n), gedomineerd door het sorteren. De lus is O(n).
• Ruimte: O(1) extra als je in-place sorteert, of O(n) voor een gesorteerde kopie.

Alternatieve kijk: aantal waarden

Een andere manier om het -1-geval te zien: met gesorteerde maxima m1 >= m2 >= ... >= mn bestaat er alleen een geldige toewijzing als het i-de grootste maximum ten minste n - i + 1 is voor elke i, aangezien je zoveel verschillende positieve waarden op of onder dat maximum nodig hebt. De lus controleert dit gaandeweg.

Randgevallen

In Java of C++ kan het totaal 32 bits overschrijden wanneer er veel torens met grote maxima zijn, dus gebruik long.

Hoe je het uitlegt in een interview

1. Herhaal de beperkingen, inclusief het -1-geval.
2. Zeg dat je hoge torens wilt met verschillende hoogtes, dus verwerk van het grootste maximum naar beneden.
3. Noem de regel: elke hoogte is het minimum van zijn maximum en één minder dan de vorige hoogte.
4. Leg uit waarom: hoogtes omwisselen tussen torens helpt niet, en elke keuze is de grootst mogelijke.
5. Geef de complexiteit en de opmerking over overflow.
6. Test met [2,2,1], één element, en allemaal gelijke waarden.

Gerelateerde oefening

Vergelijkbare greedy- en sorteerproblemen zijn Assign Cookies en Minimum Number of Arrows to Burst Balloons. Zie ons Blind 75-studieplan en AI LeetCode-tutor gids voor hoe je oefening organiseert, en de coding interview assistant gids voor reviewroutines.

Leg het uitwisselingsargument hardop uit wanneer je oefent. Een mock-interviewtranscript laat zien of je een reden gaf of alleen de code. Volg de regels van de werkgever over AI-tools bij elke live beoordeling.