Massimizza l'altezza totale delle torri uniche: soluzione greedy in Python

Massimizzare l'altezza totale di torri uniche (LeetCode 3301) ti fornisce un'altezza massima per ogni torre. Devi assegnare a ogni torre un'altezza intera positiva che non superi il suo massimo, con tutte le altezze diverse. Restituisci la somma massima possibile, oppure -1 se non è possibile. Un approccio greedy dopo l'ordinamento lo risolve in O(n log n).

Il problema

Ti viene dato un array maximumHeight, dove maximumHeight[i] è l'altezza massima consentita per la torre i. Scegli height[i] in modo che:

• 1 <= height[i] <= maximumHeight[i]
• tutti i valori height[i] siano distinti

Restituisci la somma massima possibile, oppure -1 se non esiste un'assegnazione valida.

Esempi:

L'idea

Per rendere il totale grande, vuoi ogni torre il più alta possibile. Le altezze devono essere distinte, quindi ragiona sull'ordine: la torre con il massimo più alto dovrebbe ricevere il valore più grande, la successiva il valore più grande sotto quello, e così via.

1. Ordina i massimi in ordine decrescente.
2. Assegna alla prima torre il suo massimo completo.
3. Per ogni torre successiva, assegna min(il suo massimo, altezza precedente - 1).
4. Se un'altezza assegnata scende a 0 o sotto, non esiste un'assegnazione valida, quindi restituisci -1.
5. Somma le altezze.

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

Traccia su [2,3,4,3]: ordinato in modo decrescente è [4,3,3,2]. Altezze: 4, poi min(3, 3) = 3, poi min(3, 2) = 2, poi min(2, 1) = 1. La somma è 10.

Perché il greedy funziona

Lo dimostra un argomento di scambio. Supponi che una soluzione ottimale assegni un'altezza inferiore a una torre con un massimo più grande rispetto a una con un massimo più piccolo. Scambiare le due altezze mantiene entrambe entro i loro limiti, perché la torre con il massimo più grande può assumere qualsiasi valore che poteva assumere quella più piccola, e la somma non cambia. Quindi esiste una soluzione ottimale che assegna le altezze nello stesso ordine dei massimi ordinati.

Una volta fissato l'ordine, ogni torre non può essere più alta del proprio massimo, né più alta di uno in meno rispetto alla torre precedente. Prendere esattamente quel limite superiore è la scelta migliore: un'altezza inferiore ridurrebbe la somma ora, e non aiuterebbe le torri successive, perché i loro limiti superiori dipendono da questa altezza, quindi abbassarla abbassa anche i loro.

Ho anche verificato il codice con una ricerca a forza bruta su tutte le assegnazioni su 2.000 piccoli array casuali, e le risposte coincidevano.

Complessità

• Tempo: O(n log n), dominato dall'ordinamento. Il ciclo è O(n).
• Spazio: O(1) extra se ordini sul posto, oppure O(n) per una copia ordinata.

Vista alternativa: conteggio dei valori

Un altro modo per vedere il caso -1: con i massimi ordinati m1 >= m2 >= ... >= mn, esiste un'assegnazione valida solo se l'i-esimo massimo più grande è almeno n - i + 1 per ogni i, dato che ti servono quel numero di valori positivi distinti minori o uguali ad esso. Il ciclo verifica questo mentre procede.

Casi limite

In Java o C++, il totale può superare i 32 bit quando ci sono molte torri con massimi grandi, quindi usa long.

Come spiegarlo in un colloquio

1. Riformula i vincoli, incluso il caso -1.
2. Di' che vuoi torri alte con altezze distinte, quindi procedi dal massimo più grande verso il basso.
3. Enuncia la regola: ogni altezza è il minimo tra il suo massimo e uno in meno dell'altezza precedente.
4. Spiega il perché: scambiare le altezze tra le torri non aiuta, e ogni scelta è la più grande possibile.
5. Fornisci la complessità e la nota sull'overflow.
6. Testa con [2,2,1], un solo elemento, e tutti i valori uguali.

Esercizi correlati

Problemi simili di greedy e ordinamento includono Assign Cookies e Minimum Number of Arrows to Burst Balloons. Consulta il nostro piano di studio Blind 75 e la guida al tutor AI per LeetCode per come organizzare la pratica, e la guida all'assistente per colloqui di programmazione per le routine di ripasso.

Spiega l'argomento di scambio ad alta voce quando ti eserciti. La trascrizione di un colloquio simulato mostra se hai dato una motivazione o solo il codice. Segui le regole del datore di lavoro sugli strumenti AI in qualsiasi valutazione dal vivo.