Maximiere die Gesamthöhe einzigartiger Türme: Greedy-Lösung in Python

Maximiere die Gesamthöhe eindeutiger Türme (LeetCode 3301) gibt dir eine maximale Höhe für jeden Turm. Du musst jedem Turm eine positive ganzzahlige Höhe zuweisen, die seine maximale Höhe nicht überschreitet, wobei alle Höhen unterschiedlich sein müssen. Gib die größtmögliche Gesamthöhe zurück, oder -1, wenn es nicht machbar ist. Ein Greedy-Ansatz nach dem Sortieren löst das in O(n log n).

Das Problem

Du bekommst ein Array maximumHeight, wobei maximumHeight[i] die höchste Höhe ist, die Turm i haben darf. Wähle height[i] so, dass:

• 1 <= height[i] <= maximumHeight[i]
• alle height[i]-Werte unterschiedlich sind

Gib die maximal mögliche Summe zurück, oder -1, wenn keine gültige Zuweisung existiert.

Beispiele:

Die Idee

Um die Summe groß zu machen, willst du jeden Turm so hoch wie möglich. Die Höhen müssen unterschiedlich sein, also denk an die Reihenfolge: Der Turm mit der größten erlaubten Höhe sollte den größten Wert bekommen, der nächste den größten Wert darunter, und so weiter.

1. Sortiere die Maximalwerte absteigend.
2. Gib dem ersten Turm seine volle maximale Höhe.
3. Weise jedem weiteren Turm min(seine maximale Höhe, vorherige Höhe - 1) zu.
4. Wenn eine zugewiesene Höhe auf 0 oder darunter fällt, gibt es keine gültige Zuweisung, also gib -1 zurück.
5. Addiere die Höhen.

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

Durchlauf für [2,3,4,3]: absteigend sortiert ist [4,3,3,2]. Höhen: 4, dann min(3, 3) = 3, dann min(3, 2) = 2, dann min(2, 1) = 1. Die Summe ist 10.

Warum das Greedy-Verfahren funktioniert

Ein Austauschargument zeigt es. Angenommen, eine optimale Lösung gibt einem Turm mit größerem Maximalwert eine kleinere Höhe als einem mit kleinerem Maximalwert. Das Vertauschen der beiden Höhen hält beide innerhalb ihrer Grenzen, weil der Turm mit dem größeren Maximalwert jeden Wert annehmen kann, den der kleinere annehmen könnte, und die Summe ändert sich nicht. Also weist eine optimale Lösung die Höhen in derselben Reihenfolge zu wie die sortierten Maximalwerte.

Sobald die Reihenfolge feststeht, kann jeder Turm nicht höher sein als sein eigener Maximalwert und nicht höher als eins weniger als der Turm davor. Genau diese Obergrenze zu nehmen ist am besten: Eine niedrigere Höhe würde die Summe jetzt verringern und den späteren Türmen nicht helfen, weil ihre Obergrenzen von dieser Höhe abhängen, sodass ein Absenken auch ihre nur senkt.

Ich habe den Code außerdem gegen eine Brute-Force-Suche über alle Zuweisungen auf 2.000 zufälligen kleinen Arrays geprüft, und die Ergebnisse stimmten überein.

Komplexität

• Zeit: O(n log n), dominiert vom Sortieren. Die Schleife ist O(n).
• Speicher: O(1) zusätzlich, wenn du in-place sortierst, oder O(n) für eine sortierte Kopie.

Alternative Sicht: Anzahl der Werte

Eine andere Sicht auf den -1-Fall: Bei sortierten Maximalwerten m1 >= m2 >= ... >= mn existiert eine gültige Zuweisung nur, wenn der i-t-größte Maximalwert mindestens n - i + 1 für jedes i beträgt, da du so viele verschiedene positive Werte auf oder unter ihm brauchst. Die Schleife prüft das im Verlauf.

Randfälle

In Java oder C++ kann die Summe 32 Bit überschreiten, wenn es viele Türme mit großen Maximalwerten gibt, also verwende long.

Wie du es im Interview erklärst

1. Formuliere die Einschränkungen neu, einschließlich des -1-Falls.
2. Sag, dass du hohe Türme mit unterschiedlichen Höhen willst, also verarbeite vom größten Maximalwert abwärts.
3. Nenne die Regel: Jede Höhe ist das Minimum aus ihrer maximalen Höhe und eins weniger als die vorherige Höhe.
4. Erkläre warum: Das Vertauschen von Höhen zwischen Türmen hilft nicht, und jede Wahl ist die größtmögliche.
5. Gib die Komplexität und den Überlauf-Hinweis an.
6. Teste mit [2,2,1], einem Element und lauter gleichen Werten.

Verwandte Übungen

Ähnliche Greedy- und Sortierprobleme sind Assign Cookies und Minimum Number of Arrows to Burst Balloons. Sieh dir unseren Blind-75-Lernplan und KI-LeetCode-Tutor-Leitfaden an, um zu erfahren, wie du das Üben organisierst, und den Leitfaden zum Coding-Interview-Assistenten für Wiederholungsroutinen.

Erkläre das Austauschargument laut, wenn du übst. Ein Mock-Interview-Transkript zeigt, ob du eine Begründung geliefert hast oder nur den Code. Befolge die Regeln des Arbeitgebers zu KI-Tools in jeder Live-Bewertung.