1046. 最后一块石头的重量
题目描述
输入整数数组 stones，每个元素是一块石头的重量，均为正整数。
每一轮，取出当前最重的两块石头互相撞击，设重量为 x <= y。若 x == y，两块都消失；否则重 x 的消失，另一块的重量变成 y - x 并放回。
不断重复，直到剩下的石头不足两块。返回最后剩下那块石头的重量；若一块都不剩，返回 0。
示例 1
输入：stones = [2,7,4,1,8,1] 输出：1
解释：依次撞 8 和 7、4 和 2、2 和 1、1 和 1，最后剩下一块重 1 的石头。
示例 2
输入：stones = [1] 输出：1
解释：只有一块石头，无法再撞，直接返回 1。
数据范围
1 <= stones.length <= 301 <= stones[i] <= 1000
解题思路
每回合都要“取出最大的两个”并可能“放回一个新值”，这正是大顶堆擅长的操作。Python 的 heapq 是小顶堆，所以把重量取负后入堆。弹出两次得到 y >= x，若 y > x 就把差值放回，直到堆里不足两块。
为什么正确
堆里始终是当前还存在的全部石头，堆顶是最重的一块；每回合石头数至少减少 1。
复杂度分析
时间 O(n log n)，空间 O(n)。
易错点
堆可能最后为空（例如 [5,5]），直接访问 heap[0] 会越界；另外存入小顶堆时要记得取负，放回的差值也要是负数 x - y。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
heap = [-s for s in stones]
heapq.heapify(heap)
while len(heap) > 1:
y = -heapq.heappop(heap)
x = -heapq.heappop(heap)
if y > x:
heapq.heappush(heap, x - y)
return -heap[0] if heap else 0class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
for (int s : stones) heap.offer(s);
while (heap.size() > 1) {
int y = heap.poll();
int x = heap.poll();
if (y > x) {
heap.offer(y - x);
}
}
return heap.isEmpty() ? 0 : heap.peek();
}
}class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> heap(stones.begin(), stones.end());
while (heap.size() > 1) {
int y = heap.top(); heap.pop();
int x = heap.top(); heap.pop();
if (y > x) {
heap.push(y - x);
}
}
return heap.empty() ? 0 : heap.top();
}
};type maxHeap []int
func (h maxHeap) Len() int { return len(h) }
func (h maxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h maxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *maxHeap) Push(v any) { *h = append(*h, v.(int)) }
func (h *maxHeap) Pop() any { old := *h; v := old[len(old)-1]; *h = old[:len(old)-1]; return v }
func lastStoneWeight(stones []int) int {
h := &maxHeap{}
*h = append(*h, stones...)
heap.Init(h)
for h.Len() > 1 {
y := heap.Pop(h).(int)
x := heap.Pop(h).(int)
if y > x {
heap.Push(h, y-x)
}
}
if h.Len() == 0 {
return 0
}
return (*h)[0]
}const heappush = (h, e) => {
h.push(e);
for (let i = h.length - 1, p; i > 0 && h[p = (i - 1) >> 1] < h[i]; i = p) [h[p], h[i]] = [h[i], h[p]];
};
const heappop = h => {
const top = h[0], last = h.pop();
if (h.length) {
h[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1; let s = i;
if (l < h.length && h[l] > h[s]) s = l;
if (r < h.length && h[r] > h[s]) s = r;
if (s === i) break;
[h[s], h[i]] = [h[i], h[s]]; i = s;
}
}
return top;
};
var lastStoneWeight = function(stones) {
const heap = [];
for (const s of stones) heappush(heap, s);
while (heap.length > 1) {
const y = heappop(heap);
const x = heappop(heap);
if (y > x) {
heappush(heap, y - x);
}
}
return heap.length ? heap[0] : 0;
};const heappush = (h: number[], e: number) => {
h.push(e);
for (let i = h.length - 1, p; i > 0 && h[p = (i - 1) >> 1] < h[i]; i = p) [h[p], h[i]] = [h[i], h[p]];
};
const heappop = (h: number[]) => {
const top = h[0], last = h.pop()!;
if (h.length) {
h[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1; let s = i;
if (l < h.length && h[l] > h[s]) s = l;
if (r < h.length && h[r] > h[s]) s = r;
if (s === i) break;
[h[s], h[i]] = [h[i], h[s]]; i = s;
}
}
return top;
};
function lastStoneWeight(stones: number[]): number {
const heap: number[] = [];
for (const s of stones) heappush(heap, s);
while (heap.length > 1) {
const y = heappop(heap);
const x = heappop(heap);
if (y > x) {
heappush(heap, y - x);
}
}
return heap.length ? heap[0] : 0;
}