Last Stone Weight

Q: Какова временная сложность задачи Last Stone Weight?

С max-кучей не более n-1 раундов, в каждом из которых выполняются две операции извлечения и одна операция добавления, занимают O(n log n) времени и O(n) памяти. Сортировка всей кучи в каждом раунде занимает O(n² log n) .

ЛегкоКуча

+10

У тебя есть куча камней, а stones[i] — это вес камня i. В каждом раунде бери два самых тяжёлых камня и разбивай их друг о друга. Если они весят одинаково, оба уничтожаются. Если нет, более лёгкий камень уничтожается, а более тяжёлый уменьшается на разницу между их весами.

Напиши lastStoneWeight, которая проводит раунды, пока не останется не более одного камня, и возвращает его вес или 0, если камней не осталось.

Функция

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: веса камней в куче
Возвращаетinteger: вес последнего камня или 0, если камней не осталось

Ограничения

1 ≤ stones.length ≤ 10⁴
1 ≤ stones[i] ≤ 1000

Примеры

Ввод: stones = [3, 9, 4, 6, 2]
Вывод: 0
Пояснение: 9 и 6 оставляют 3, затем 4 и 3 оставляют 1, затем 3 и 2 оставляют ещё один 1. Два камня весом 1 уничтожают друг друга, поэтому ответ — 0.

Ввод: stones = [10, 4, 1]
Вывод: 5
Пояснение: 10 и 4 дают 6, а 6 и 1 дают 5. Остаётся один камень весом 5.

Ввод: stones = [8]
Вывод: 8
Пояснение: Один камень не с чем разбить, поэтому его вес 8 и есть ответ.

Дополнительный вопрос

Веса не превышают 1000. Можешь ли ты использовать это ограничение, чтобы решить задачу за время O(n + W), где W — наибольший вес, без кучи?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Не существует формулы, позволяющей пропустить ходы вперёд: ты играешь в каждом раунде. В каждом раунде нужны два самых тяжёлых камня из кучи, которая постоянно меняется, потому что разбитый камень может вернуться более лёгким. Максимальная куча выдаёт самый тяжёлый камень и принимает новый за O(log n).

Сортируй груду в каждом раунде

Верно, но не успевает на самых больших тестах

Идея

Следуй правилам буквально: отсортируй кучу, сними два самых тяжёлых камня с конца и положи их разность обратно, если она не равна нулю. Сортируй заново в каждом раунде, потому что разность может оказаться где угодно. В первом примере из 9 и 6 получается 3, которое нужно поместить перед 4.

В каждом раунде удаляется как минимум один камень, поэтому раундов будет не больше n-1, и в каждом раунде сортируется до n камней: O(n² log n). При n = 10^4 это около 10^4 сортировок до 10^4 чисел.

Алгоритм

Скопируй камни в список с именем pile.
Пока в куче больше одного камня, сортируй её по возрастанию.
Убери два последних камня: heaviest и second.
Если они различаются, добавь heaviest - second обратно в кучу.
Верни оставшийся камень или 0, если куча пуста.

def lastStoneWeight(stones):
    pile = list(stones)
    while len(pile) > 1:
        pile.sort()  # the two heaviest stones move to the end
        heaviest = pile.pop()
        second = pile.pop()
        if heaviest != second:
            pile.append(heaviest - second)
    return pile[0] if pile else 0

Максимальная куча

Идея

Максимальная куча хранит наибольшее значение наверху, а удаление верхнего элемента или добавление значения занимает O(log n). Поместите в неё все камни. В каждом раунде извлекайте два элемента — два самых тяжёлых камня — и возвращайте разность, если она не равна нулю; куча переместит её на нужное место. Для [10, 4, 1] извлеките 10 и 4 и добавьте 6, затем извлеките 6 и 1 и добавьте 5.

Будет не более n-1 раундов, в каждом из которых выполняются два извлечения и одно добавление, поэтому время работы составляет O(n log n), а объём памяти — O(n). В языках без встроенной кучи решение хранит её в массиве, где родитель элемента с индексом i находится по индексу (i-1)/2.

Алгоритм

Поместите каждый камень в максимальную кучу.
Пока в куче больше одного камня, извлекайте самый тяжёлый, а затем второй по тяжести.
Если они различаются, добавьте heaviest - second.
Верните верхний элемент кучи или 0, если она пуста.

import heapq


def lastStoneWeight(stones):
    # heapq is a min-heap, so store negated weights: the smallest entry is the heaviest stone.
    heap = [-w for w in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        heaviest = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if heaviest != second:
            heapq.heappush(heap, -(heaviest - second))
    return -heap[0] if heap else 0

Ловушки и крайние случаи

Возврат верхнего элемента пустой кучи. Когда две последние камня весят одинаково, как в первом примере, ничего не остаётся, и ответ — 0.
Случайное использование минимальной кучи. Python's heapq и стандартный PriorityQueue в Java выдают наименьшее значение; инвертируйте веса или передайте компаратор в обратном порядке.
Забыть о знаке при инвертированных весах. Оба извлечённых значения отрицательны, поэтому значение для добавления — -(heaviest - second).
Однократная сортировка в начале и проход по списку. Разность может быть меньше весов камней, до которых вы ещё не добрались, поэтому после первого раунда порядок перестаёт быть актуальным.

Частые вопросы3

Какова временная сложность задачи Last Stone Weight?

С max-кучей не более n-1 раундов, в каждом из которых выполняются две операции извлечения и одна операция добавления, занимают O(n log n) времени и O(n) памяти. Сортировка всей кучи в каждом раунде занимает O(n² log n).

Почему для Last Stone Weight используется куча, а не отсортированный список?

Отсортированный список сразу даёт два самых тяжёлых камня, но повторная сортировка после добавления разницы сдвигает до n элементов, что суммарно за все раунды составляет O(n²). Куча позволяет узнать только «какое значение наибольшее» и добавить новое значение — и то и другое за O(log n), а именно это и требуется для симуляции.

Меняет ли порядок разбивания камней одинакового веса ответ?

Нет. Если несколько камней имеют наибольший вес, то какие бы два ты ни выбрал, они будут весить одинаково, поэтому после раунда в куче останутся камни с теми же весами. Ответ зависит только от весов.

def lastStoneWeight(stones):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

stones = [3, 9, 4, 6, 2]

Ожидаемый вывод