💬 Discord
Sign In
NeetCode #524LC-1046EasyHeap / Priority QueueNC 150NC 250
← Back to All Problems

#524 · #1046 · Last Stone Weight(最后一块石头的重量)

📌 Problem Statement & Constraints

You are given an array stones of weights. Repeatedly pick the two heaviest stones: if they are equal both are destroyed, otherwise the lighter is destroyed and the heavier becomes the difference. Return the weight of the last remaining stone, or 0 if none remain. Constraints: 1 <= stones.length <= 30, 1 <= stones[i] <= 1000.

💡 Core Algorithmic Approaches

  1. A max-heap (a negated min-heap in Python) gives the two heaviest stones in O(log n) each.
  2. Pop two, push the difference back when non-zero.
  3. Repeat until fewer than two stones remain.
  4. The result is the single remaining stone's weight, or 0.

💻 Benchmark Python3 Implementation

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        import heapq
        h = [-s for s in stones]           # negate for a max-heap
        heapq.heapify(h)
        while len(h) > 1:
            a = -heapq.heappop(h)          # heaviest
            b = -heapq.heappop(h)          # second heaviest
            if a != b:
                heapq.heappush(h, -(a - b))   # the remainder stays
        return -h[0] if h else 0

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): each of the O(n) rounds costs O(log n).
💾 Space Complexity
O(n) for the heap.

⚠️ Interview Pitfalls & Follow-ups

  • Using a min-heap directly: the two heaviest stones would not be accessible; negation is the Python idiom.
  • Pushing the difference when it is zero: both stones are destroyed, so nothing should be pushed.
  • Returning the heap contents: the answer is the single remaining weight, or 0 when the heap is empty.
  • Sorting repeatedly: O(n^2 log n).