Last Stone Weight

Q: Какова временная сложность задачи «Последний вес камня»?

С max-heap построение кучи и проведение не более 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 и есть ответ.

+13 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

Буквально следуй правилам. Отсортируй кучу так, чтобы два самых тяжёлых камня оказались в конце, убери их, а если их вес различается, верни разницу обратно. Повторяй, пока в куче не останется один камень или ни одного.

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

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

Алгоритм

Скопируй камни в список под названием 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

Макс-куча

Идея

В каждом раунде нужны только самые большие камни, полный порядок не нужен. Для этого создаётся max-heap: он хранит наибольшее значение наверху, а удаление верхнего элемента или добавление значения стоит O(log n).

Помести каждый камень в кучу. В каждом раунде извлеки два верхних элемента, чтобы получить два самых тяжёлых камня. Если они различаются, добавь разницу обратно; куча сама переместит её на правильное место. Для [10, 4, 1] ты извлекаешь 10 и 4 и добавляешь 6, затем извлекаешь 6 и 1 и добавляешь 5, и в куче остаётся только 5.

Будет не более n-1 раундов, в каждом — два извлечения и не более одного добавления, поэтому время работы составляет O(n log n), а куча использует O(n) памяти. В некоторых языках есть встроенная куча: heapq в Python — это min-heap, поэтому в ней хранятся веса с противоположным знаком; в Java есть PriorityQueue, в C++ — priority_queue, в Go — container/heap, в Rust — BinaryHeap, а в PHP — SplMaxHeap. В остальных языках решение реализует собственную кучу в массиве: родитель элемента с индексом i находится по индексу (i-1)/2, а новое значение поднимается вверх, пока оно больше родительского.

Алгоритм

Помести каждый камень в max-heap.
Пока в куче больше одного камня, извлекай самый тяжёлый, а затем второй по тяжести.
Если они различаются, добавь 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-овский heapq и стандартный PriorityQueue в Java выдают наименьшее значение; инвертируй веса или передай компаратор в обратном порядке.
Забыть выполнить обратное инвертирование. При использовании heapq оба извлечённых значения отрицательны, поэтому разность, которую ты добавляешь, равна -(heaviest - second).
Отсортировать список один раз в начале и пройти по нему. Разность весов двух камней может быть меньше весов камней, которых ты ещё не касался, поэтому фиксированный порядок устаревает уже после первого раунда.

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

Какова временная сложность задачи «Последний вес камня»?

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

Зачем использовать кучу для Last Stone Weight?

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

Можно ли решить задачу Last Stone Weight без кучи?

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

Меняет ли порядок уничтожения камней одинакового веса ответ?

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

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается