Go语言 LeetCode 1046：最后一块石头的重量解法

题目描述

有一堆石头，每块石头的重量都是正整数。每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。

• 如果选出的两块石头重量 $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]。

思路分析

这道题的关键在于“总是选取最重的两块”。如果使用排序数组，每次取走元素并插入新重量后都需要重新排序，时间复杂度较高。

更高效的方案是使用优先队列（Priority Queue）或最大堆（Max Heap）。

1. 准备条件：创建一个支持自定义比较逻辑的最大堆结构。在 Go 中，我们可以实现 `container/heap` 接口来定制一个 IntHeap。
2. 真实操作顺序：
   - 将所有石头重量推入堆中。
   - 循环直到堆中只剩 0 个或 1 个元素：
     - 弹出最大的石头 $y$。
     - 弹出第二大的石头 $x$。
     - 计算差值 $diff = y - x$。
     - 如果 $diff > 0$，将 $diff$ 重新推入堆中。
3. 完成判断：如果堆为空，返回 0；否则返回剩余的最后一个元素。

AC 代码

以下是使用 Go 语言实现的完整代码，包含完整的 Max Heap 接口定义及主逻辑：

package main

import (
	"container/heap"
)

// 定义最大堆结构
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] } // 大于号实现最大堆
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	item := old[n-1]
	old[n-1] = nil // avoid memory leak
	*h = old[0 : n-1]
	return item
}

func lastStoneWeight(stones []int) int {
	h := &IntHeap(stones)
	heap.Init(h)

	for h.Len() > 1 {
		a := heap.Pop(h).(int) // 最重
		b := heap.Pop(h).(int) // 次重
		if a != b {
			heap.Push(h, a-b)
		}
	}

	if h.Len() == 0 {
		return 0
	}
	return (*h)[0]
}

通过优先队列，我们避免了频繁的整体排序，使得整体时间复杂度优化至 $O(N \log N)$。以上就是Go语言 LeetCode 1046 最后一块石头的重量解法的详细内容，更多关于Go算法题解的资料请关注本站其它相关文章！