Day 9：1046. Last Stone Weight

今日题目

题目连结：1046. Last Stone Weight
题目主题：Array, Heap(Priority Queue)

今天的重点一样在Heap (Priority Queue)这个主题上面，这次会分享Heap (Priority Queue)实际上长的样子及pop资料的过程。

简单说说 Heap(Priority Queue)

上一篇分享了Heap的使用概念，另外也有提到Heap其实是一个Tree的结构，这次就拿一个范例，来看看将阵列放进箱子後，实际上会长成什麽样子。范例一样使用Min Heap来说明，以Python为例，当我们呼叫了heapify()实际上，到底对阵列做了什麽改变？而heappop()又是怎麽运作的呢？

范例资料：nums = [13, 14, 11, 1, 4, 6, 16]

当我们将这个nums的资料转成Min Heap後，也就是使用heapify(nums)後，实际上这个资料转换後的结构长相如下图。

这种树的原则是越上层的数字越小，越下层的数字越大，数字不见得会依照顺序排，但上层小、下层大的原则是一定的。假设是Max Heap，原则是越上层的数字越大，越下层的数字越小。

还记得前一篇讲到当我们对这个Min Heap取一笔资料时，一定会优先取得最小的数字，这个资料的取得过程，实际上运作如下图：

1. 最上面的最小数字会跟最下层的最後一个数字交换，这个最小数字就会被pop移出这棵树了。
2. 而移到上面的目的是要让原则保持下去，因此这个被换上来的数字会开始往下层子节点去找，它会跟下层子节点中最小的数字交换。
3. 若有交换，会继续做第 2 步骤一样的事，直到下层子节点的数字比较大或没有子节点才会停下来。

再让我们看一个例子，如果在取一笔资料，运作过程会如下图：

可以看到这个数字 11 被换到最上面以後，这次是往下层右子节点走，是因为 6 是它下层子节点中最小的，换完以後就停止了，因为没有下层没有子节点了。

可以在上面两个pop例子中看到，这棵树在取完资料的过程，会一直保持树的原则，越上层的数字越小，越下层的数字越大。

这是本系列文第一次看到树的结构，接下来会越来越多树的例子，在这边我们只要先知道Heap(Priority Queue)实际的长相及pop运作过程即可。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

本题会输入一个stones阵列，这个阵列存放的每个值代表一颗石头的重量。
这是一个游戏，每回合会选两颗最重的石头互敲敲碎，假设最重的两颗石头分别为 x 及 y，敲碎的规则如下：

• x == y，这两颗石头都会完全被销毁。
• x != y，x 会被销毁，而 y 会变成一颗重量为 y - x 的石头。

依照上面的规则，会一直玩到剩下一颗石头或是没有石头才会结束游戏。最终如果剩一颗石头，回传最後这颗石头的重量，若最终没有任何石头，直接回传０。

约束：

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

范例1

输入: stones = [2,7,4,1,8,1]
输出: 1
解释: 
第一回合 最重两颗石头为 7 跟 8 ，敲完以後会拿到 1 这颗石头，放回stones中，剩[2,4,1,1,1]。
第二回合 最重两颗石头为 2 跟 4 ，敲完以後会拿到 2 这颗石头，放回stones中，剩[2,1,1,1]。
第三回合 最重两颗石头为 2 跟 1 ，敲完以後会拿到 1 这颗石头，放回stones中，剩[1,1,1]。
第四回合 最重两颗石头为 1 跟 1 ，敲完以後两颗都被销毁，stones中剩[1]。
最後回传这颗石头重量 1。

范例2

输入: stones = [1]
输出: 1
解释: 因为只有一颗石头，直接回传这颗石头的重量。

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 使用Max Heap来处理。
2. 跑一个回圈，每圈都从Max Heap取两个值出来:
   • 第一个值放进 y、第二个值放进 x
   • y - x 取得y石头的新重量。
   • 若新的重量大於 0 要再放回Max Heap，继续下一次的游戏。
   • 若石头剩一颗或没有石头时结束回圈。
3. 如果石头剩一颗，回传这颗石头的重量，若没有石头回传 0。

图解过程

范例: stones = [2,7,4,1,8,1]

上图范例可以看到，每个步骤会取得两颗石头，step2 开始会看到的绿色数字，就是前一步骤中y - x 得到的新石头重量。直接看step4 取到的 y 跟 x 都是1，因此直接抵销，最终step 5 剩一个石头，所以回传这颗石头结束。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

from heapq import _heapify_max, _heappop_max, heappush

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # 跑一个回圈，到剩一颗石头或没石头时结束
        while len(stones) > 1:
            # 整理成Max Heap的结构
            _heapify_max(stones)
            # 最重的石头放 y
            y = _heappop_max(stones)
            # 第二重的石头放 x
            x = _heappop_max(stones)
            # 取得新重量
            newWeight = y-x
            # 若不是 0，要再把这颗有新重量的石头放回stones中
            if newWeight > 0:
                heappush(stones, newWeight)
        # 若剩一颗，回传这颗石头重量
        # 若没有剩任何石头回传 0
        return stones[0] if len(stones) == 1 else 0

希望您今天能了解到...

1. Heap(Priority Queue) 的真面目
2. 1046. Last Stone Weight 解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：144. Binary Tree Preorder Traversal