LEETCODE 1046. Last Stone Weight 解题思路分析

题目大意：

最后一块石头的重量

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

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

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

提示：

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1046

解题思路分析：

题目要求每次要取出数组中最大的两个数相互伤害，进行粉碎操作，这就牵扯到排序问题。另外粉碎后得到的新数字如果大于0，还要将其加入到数组中再次排序，以便接下来再取最大值时使用。在java语言中，使用PriorityQueue类是最方便的选择，因为PriorityQueue获取元素时，它会自动返回给我们Queue中优先级最高的数值，这省去了排序工作，我们只需要负责存和取就可以了。需要注意的一点是， PriorityQueue在保存数字时，默认的优先级顺序是数字有小到大排序，数字越小优先度越高，然而题目要求取最大值，因此，在初始化PriorityQueue时，要指定反向排序。

回到本题，我们先将数组中所有的数字添加到Queue中，接下来，由于PriorityQueue已帮我们做好排序，我们利用poll方法直接取两个数字即可，取到的数字肯定是最大的两个。然后再将两数做减法，如果结果大于0，再将此结果添加到Queue中，重复上面的操作，直到Queue中只剩下1个或0个元素为止。

这时如果Queue为空，说明所有元素已经全部粉碎。如果 Queue 的大小为1，直接返回这个元素即可。

完整代码：

public int lastStoneWeight(int[] stones) {
    // 定义一个优先级Queue。注意指定优先级为反序
    PriorityQueue<Integer> q= 
        new PriorityQueue<>(stones.length,Collections.reverseOrder());
    for(int stone : stones){ // 将所有数值添加到Queue
        q.offer(stone);
    }
    while(q.size()>1){ // 只要Queue的大小大于1，保持循环
        int n = q.poll() - q.poll(); // 取出Queue中前两个元素相减
        if(n>0){ // 如果差大于0，将其加入到Queue中
            q.offer(n);
        }
    }
    return q.size()==0 ? 0 : q.poll();
}

本解法运行时间为1ms。

Runtime: 1 ms, faster than 96.42% of Java online submissions for Last Stone Weight.

Memory Usage: 34 MB, less than 100.00% of Java online submissions for Last Stone Weight.

本题还有续集，LEETCODE 1049. Last Stone Weight II，不过解题思路完全不同，有兴趣的话可以参考我之前的文章。LEETCODE 1049. Last Stone Weight II 解题思路分析

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1046-last-stone-weight-解题思路分析/