Maximize a Altura Total de Torres Únicas: Solução Gulosa em Python

Maximizar a Altura Total de Torres Únicas (LeetCode 3301) fornece uma altura máxima para cada torre. Você deve atribuir a cada torre uma altura inteira positiva que não exceda seu máximo, com todas as alturas diferentes. Retorne a maior soma possível, ou -1 se não for possível. Uma abordagem gulosa após ordenar resolve em O(n log n).

O problema

Você recebe um array maximumHeight, onde maximumHeight[i] é a torre mais alta que i pode ser. Escolha height[i] de forma que:

• 1 <= height[i] <= maximumHeight[i]
• todos os valores de height[i] sejam distintos

Retorne a soma máxima possível, ou -1 se não existir atribuição válida.

Exemplos:

A ideia

Para tornar o total grande, você quer cada torre o mais alta possível. As alturas devem ser distintas, então pense na ordem: a torre mais alta permitida deve receber o maior valor, a próxima o maior valor abaixo desse, e assim por diante.

1. Ordene os máximos em ordem decrescente.
2. Dê à primeira torre seu máximo completo.
3. Para cada próxima torre, atribua min(seu máximo, altura anterior - 1).
4. Se uma altura atribuída cair para 0 ou menos, não há atribuição válida, então retorne -1.
5. Some as 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

Trace em [2,3,4,3]: ordenado decrescente é [4,3,3,2]. Alturas: 4, depois min(3, 3) = 3, depois min(3, 2) = 2, depois min(2, 1) = 1. A soma é 10.

Por que o guloso funciona

Um argumento de troca mostra isso. Suponha que uma solução ótima dê uma altura menor a uma torre com máximo maior do que a uma com máximo menor. Trocar as duas alturas mantém ambas dentro de seus limites, porque a torre com o máximo maior pode assumir qualquer valor que a menor poderia, e a soma não muda. Então alguma solução ótima atribui alturas na mesma ordem que os máximos ordenados.

Uma vez que a ordem está fixada, cada torre não pode ser mais alta que seu próprio máximo, nem mais alta que uma unidade a menos que a torre anterior. Tomar exatamente esse limite superior é o melhor: uma altura menor reduziria a soma agora, e não ajudaria as torres posteriores, porque seus limites superiores dependem dessa altura, então diminuí-la só diminui os deles também.

Também verifiquei o código contra uma busca por força bruta sobre todas as atribuições em 2.000 arrays pequenos aleatórios, e as respostas coincidiram.

Complexidade

• Tempo: O(n log n), dominado pela ordenação. O loop é O(n).
• Espaço: O(1) extra se você ordenar no lugar, ou O(n) para uma cópia ordenada.

Visão alternativa: contagem de valores

Outra forma de ver o caso -1: com máximos ordenados m1 >= m2 >= ... >= mn, uma atribuição válida existe apenas se o i-ésimo maior máximo for pelo menos n - i + 1 para cada i, já que você precisa dessa quantidade de valores positivos distintos iguais ou abaixo dele. O loop verifica isso à medida que avança.

Casos extremos

Em Java ou C++, o total pode exceder 32 bits quando há muitas torres com máximos grandes, então use long.

Como explicar em uma entrevista

1. Reafirme as restrições, incluindo o caso -1.
2. Diga que você quer torres altas com alturas distintas, então processe do maior máximo para baixo.
3. Declare a regra: cada altura é o mínimo entre seu máximo e uma unidade a menos que a altura anterior.
4. Explique por quê: trocar alturas entre torres não ajuda, e cada escolha é a maior possível.
5. Dê a complexidade e a observação sobre overflow.
6. Teste com [2,2,1], um elemento, e todos os valores iguais.

Prática relacionada

Problemas similares de guloso e ordenação incluem Assign Cookies e Minimum Number of Arrows to Burst Balloons. Veja nosso plano de estudo Blind 75 e guia de tutor de IA para LeetCode para como organizar a prática, e o guia de assistente para entrevista de programação para rotinas de revisão.

Explique o argumento de troca em voz alta quando praticar. Uma transcrição de entrevista simulada mostra se você deu uma razão ou apenas o código. Siga as regras do empregador sobre ferramentas de IA em qualquer avaliação ao vivo.