Максимизация общей высоты уникальных башен: жадное решение на Python

Максимизация общей высоты уникальных башен (LeetCode 3301) даёт вам максимальную высоту для каждой башни. Нужно присвоить каждой башне целочисленную положительную высоту, не превышающую её максимум, причём все высоты должны быть разными. Верните наибольшую возможную сумму высот или -1, если это невозможно. Жадный подход после сортировки решает задачу за O(n log n).

Задача

Дан массив maximumHeight, где maximumHeight[i] — максимально допустимая высота башни i. Выберите height[i] так, чтобы:

• 1 <= height[i] <= maximumHeight[i]
• все значения height[i] были различны

Верните максимально возможную сумму или -1, если допустимого набора высот не существует.

Примеры:

Идея

Чтобы сумма была как можно больше, каждую башню хочется сделать повыше. Высоты должны быть различными, поэтому подумайте о порядке: самая высокая из допустимых башен должна получить наибольшее значение, следующая — наибольшее значение меньше него, и так далее.

1. Отсортируйте максимумы по убыванию.
2. Первой башне присвойте её полный максимум.
3. Для каждой следующей башни присваивайте min(её максимум, предыдущая высота - 1).
4. Если присваиваемая высота становится равной 0 или меньше, допустимого набора не существует — верните -1.
5. Сложите все высоты.

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

Проследим на [2,3,4,3]: после сортировки по убыванию получаем [4,3,3,2]. Высоты: 4, затем min(3, 3) = 3, затем min(3, 2) = 2, затем min(2, 1) = 1. Сумма равна 10.

Почему жадный алгоритм работает

Это доказывается аргументом обмена. Предположим, в оптимальном решении башне с большим максимумом досталась меньшая высота, чем башне с меньшим максимумом. Если поменять эти высоты местами, обе останутся в своих пределах: башня с большим максимумом может принять любое значение, которое могла принять меньшая, а сумма не изменится. Значит, существует оптимальное решение, в котором высоты назначаются в том же порядке, что и отсортированные максимумы.

Когда порядок зафиксирован, каждая башня не может быть выше своего максимума и не может быть выше предыдущей башни минус один. Взять ровно эту верхнюю границу — оптимально: меньшая высота уменьшила бы сумму сейчас и не помогла бы последующим башням, потому что их верхние границы зависят от этой высоты, так что её понижение только понижает и их.

Я также сверил код с полным перебором всех вариантов на 2 000 случайных небольших массивах — ответы совпали.

Сложность

• Время: O(n log n), определяется сортировкой. Цикл занимает O(n).
• Память: O(1) дополнительно при сортировке на месте или O(n) для отсортированной копии.

Другой взгляд: количество значений

На случай -1 можно посмотреть и так: при отсортированных максимумах m1 >= m2 >= ... >= mn допустимый набор существует только если i-й по величине максимум не меньше n - i + 1 для каждого i, поскольку нужно ровно столько различных положительных значений, не превышающих его. Цикл проверяет это по ходу дела.

Краевые случаи

В Java или C++ сумма может превысить 32 бита, когда башен много и у них большие максимумы, поэтому используйте long.

Как объяснить это на собеседовании

1. Переформулируйте ограничения, включая случай -1.
2. Скажите, что вам нужны высокие башни с различными высотами, поэтому обрабатывайте максимумы от большего к меньшему.
3. Сформулируйте правило: каждая высота — это минимум из её максимума и предыдущей высоты минус один.
4. Объясните почему: обмен высотами между башнями не помогает, а каждый выбор — максимально возможный.
5. Назовите сложность и упомяните про переполнение.
6. Проверьте на [2,2,1], на одном элементе и на всех равных значениях.

Похожие задачи для практики

Похожие жадные задачи и задачи на сортировку — Assign Cookies и Minimum Number of Arrows to Burst Balloons. Смотрите наш план подготовки Blind 75 и руководство по AI-тренажёру для LeetCode, чтобы организовать практику, а также руководство по ассистенту для собеседований по программированию для routines повторения.

Проговаривайте аргумент обмена вслух во время практики. Транскрипт mock-интервью показывает, привели ли вы обоснование или только код. Соблюдайте правила работодателя об использовании AI-инструментов на любом живом собеседовании.