What is the best approach for solving the Last Stone Weight problem?

Using a max-heap provides the most efficient solution for the Last Stone Weight problem by allowing quick retrieval and modification of the two largest stones.

Can I solve the problem with sorting?

Yes, sorting works as an alternative approach, though it's less efficient than using a heap. Sorting allows easy access to the two largest stones but involves higher time complexity.

How do I handle edge cases in this problem?

Edge cases like a single stone or stones with identical weights can be handled by checking the length of the array or ensuring no unnecessary operations are performed when only one stone remains.

How does GhostInterview help with Last Stone Weight?

GhostInterview provides step-by-step assistance in understanding heap and sorting methods, helping you implement a clear and efficient solution.

What is the time complexity of the heap solution?

The heap solution has a time complexity of O(n log n), where n is the number of stones, due to repeated heap insertions and extractions.

#1046

Easy

auto_awesome堆

LeetCode 题解工作台

最后一块石头的重量

有一堆石头，每块石头的重量都是正整数。每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y ，且 x 。那么粉碎的可能结果如下：如果 x == y ，那么两块石头都会被完全粉碎；如果 x != y ，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头…

数组堆（优先队列）

题目描述

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例：

输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 1000

lightbulb

解题思路

方法一：优先队列（大根堆）

我们将数组 stones 所有元素放入大根堆，然后执行循环操作，每次弹出两个元素 $y$ 和 $x$ ，如果 $x \neq y$ ，将 $y - x$ 放入大根堆。当堆元素个数小于 $2$ 时，退出循环。

最后如果存在堆顶元素，则将其返回，否则返回 $0$ 。

时间复杂度 $O(n\log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 stones 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        h = [-x for x in stones]
        heapify(h)
        while len(h) > 1:
            y, x = -heappop(h), -heappop(h)
            if x != y:
                heappush(h, x - y)
        return 0 if not h else -h[0]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate uses efficient heap operations to solve the problem.
question_mark
Candidate explains the trade-off between heaps and sorting for this problem.
question_mark
Candidate demonstrates how to handle edge cases such as one stone or identical stones.

warning

常见陷阱

外企场景

error
Not using a heap efficiently, leading to higher time complexity than necessary.
error
Over-complicating the solution with unnecessary steps when the problem can be solved with basic sorting or heaps.
error
Failing to handle the case where only one stone remains.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Extend the problem to handle different game variations where the number of stones can be modified after each turn.
arrow_right_alt
Instead of smashing stones, consider keeping track of the two smallest stones.
arrow_right_alt
Adjust the problem to allow multiple rounds of stone smashing, where new stones are added to the array after each turn.

help

常见问题

外企场景

继续练习

#1054 距离相等的条形码 #1094 拼车 #973 最接近原点的 K 个点