LeetCode: 1046 Last Stone Weight

You are given an array of integers stones where stones[i] is the weight of the i-th stone.

We are playing a game with the stones. On each turn, we choose the two heaviest stones and smash them together. Suppose the heaviest stone has a weight x and the second heaviest stone has a weight y (where x <= y). The result of this smash is:

If x == y, both stones are destroyed.
If x != y, the stone of weight x is destroyed, and the stone of weight y has a new weight of y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Example

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
We smash 7 and 8 together. Resulting stones are [2,4,1,1,1] and 1.
Then we smash 4 and 2 together. Resulting stones are [2,1,1,1].
Then we smash 2 and 1 together. Resulting stones are [1,1,1].
Then we smash 1 and 1 together. Resulting stones are [1].

问题

给定一个整数数组 stones，其中 stones[i] 是第 i 块石头的重量。

我们用这些石头玩一个游戏。在每一回合中，我们选择两块最重的石头并将它们相互碰撞。假设最重的石头重量为 x，第二重的石头重量为 y（x <= y）。碰撞的结果如下：

如果 x == y，两块石头都会被摧毁。
如果 x != y，重量为 x 的石头被摧毁，重量为 y 的石头的重量变为 y - x。

游戏结束后，最多只剩下一块石头。

返回最后剩下的石头的重量。如果没有石头剩下，返回 0。

例子

输入: stones = [2,7,4,1,8,1]
输出: 1
解释: 
我们碰撞了 7 和 8。结果石头变为 [2,4,1,1,1] 和 1。
然后我们碰撞了 4 和 2。结果石头变为 [2,1,1,1]。
然后我们碰撞了 2 和 1。结果石头变为 [1,1,1]。
然后我们碰撞了 1 和 1。结果石头变为 [1]。

Iterative Solution

Approach: Max Heap / 最大堆

The key to solving this problem efficiently is using a max heap to always get the two largest stones. In Python, the heapq library only supports a min heap, so we simulate a max heap by negating the values in the heap.

Approach Explanation / 方法解释

Use Max Heap: By negating the weights of the stones, we can use a min heap as a max heap.
Heap Operations: On each iteration, pop the two largest stones, smash them, and push the result back into the heap if there’s a remainder.
End Condition: When one or no stones remain, return the last stone or 0.

Iterative Algorithm / 迭代算法

Negate all the stone weights and push them into a heap.
While there is more than one stone left:
- Pop the two largest stones from the heap.
- If they are not equal, push the difference back into the heap.
Return the last remaining stone or 0 if none are left.

Iterative Implementation / 迭代实现

import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # Use max heap by negating values
        max_heap = [-stone for stone in stones]
        heapq.heapify(max_heap)

        # Smash the two largest stones until one or none are left
        while len(max_heap) > 1:
            # Pop two largest stones
            first = -heapq.heappop(max_heap)
            second = -heapq.heappop(max_heap)

            # If they are not equal, push the remainder
            if first != second:
                heapq.heappush(max_heap, -(first - second))

        # Return the last remaining stone or 0
        return -max_heap[0] if max_heap else 0

Iterative Solution Explanation / 迭代解决方案解释

Create Max Heap / 创建最大堆
```
max_heap = [-stone for stone in stones]
heapq.heapify(max_heap)
```
- English: Negate all the stone weights and heapify them to create a max heap.
- Chinese: 将所有石头的重量取负数并进行堆化操作以创建最大堆。
Smash Two Largest Stones / 碰撞两块最重的石头
```
while len(max_heap) > 1:
   first = -heapq.heappop(max_heap)
   second = -heapq.heappop(max_heap)
```
- English: Continue popping the two largest stones until one or none are left.
- Chinese: 不断弹出两块最重的石头，直到只剩下一块或没有石头。
Return Last Stone / 返回最后的石头
```
return -max_heap[0] if max_heap else 0
```
- English: If there’s one stone left, return its value; otherwise, return 0.
- Chinese: 如果只剩下一块石头，返回其值；否则返回 0。

Recursive Solution

Approach: Recursive Max Heap Simulation / 递归最大堆模拟

We can simulate the smashing process recursively by continuously finding the two largest stones and reducing the problem size in each recursion step. The heap operations can be incorporated into each recursive call.

Recursive Algorithm / 递归算法

Negate the values to simulate a max heap and heapify the list.
Recursively smash the two largest stones until only one or none remain.
Return the weight of the last stone or 0.

Recursive Implementation / 递归实现

import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        def smash_stones(max_heap):
            if len(max_heap) <= 1:
                return -max_heap[0] if max_heap else 0

            first = -heapq.heappop(max_heap)
            second = -heapq.heappop(max_heap)

            if first != second:
                heapq.heappush(max_heap, -(first - second))

            return smash_stones(max_heap)

        # Negate all stones to use as max heap
        max_heap = [-stone for stone in stones]
        heapq.heapify(max_heap)

        return smash_stones(max_heap)

Recursive Solution Explanation / 递归解决方案解释

Base Case / 基本情况
```
if len(max_heap) <= 1:
   return -max_heap[0] if max_heap else 0
```
- English: If one or no stones are left, return the last stone or 0.
- Chinese: 如果只剩下一块或没有石头，返回最后的石头或 0。
Recursive Smash / 递归碰撞
```
first = -heapq.heappop(max_heap)
second = -heapq.heappop(max_heap)
if first != second:
   heapq.heappush(max_heap, -(first - second))
return smash_stones(max_heap)
```
- English: Pop the two largest stones and recursively continue the process. If they are not equal, push the remainder back into the heap.
- Chinese: 弹出两块最重的石头并递归继续这个过程。如果它们不相等，则将剩余的重量压入堆中。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(n log n), where n is the number of stones. Each heap operation takes O(log n), and we perform it n - 1 times.
Space Complexity / 空间复杂度:
- Iterative Solution: O(n), due to the space required by the heap.
- Recursive Solution: O(n), due to the heap and the recursion stack.

Key Concept / 关键概念

Max Heap / 最大堆: A max heap allows us to efficiently extract the two largest stones. By using a min heap and negating the values, we can simulate a max heap in Python.
**

Recursion / 递归**: The recursive solution uses a divide-and-conquer approach, reducing the problem size at each step by smashing the two largest stones.

Summary / 总结

English: We can solve the problem of finding the last stone weight by using a max heap. Both iterative and recursive solutions use heap operations to efficiently smash the two largest stones until one remains.
Chinese: 我们可以通过使用最大堆解决找到最后一块石头重量的问题。迭代和递归解决方案都使用堆操作来高效地碰撞两块最重的石头，直到只剩下一块。

Tips / 提示

English: Max heaps are useful in problems where you need to frequently extract the largest elements. Simulating a max heap using a min heap is a common technique in Python.
Chinese: 最大堆在需要频繁提取最大元素的问题中非常有用。在 Python 中，用最小堆模拟最大堆是常见的技术。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice heap-based problems to get comfortable with heap operations and understand how to use them to efficiently manage priority elements.
Chinese: 练习基于堆的问题，熟悉堆操作，并了解如何使用它们高效管理优先元素。

Post Views: 9

CODEBITWAVE