【Leetcode Daily】1046最后一块石头的重量

发表于2025-12-10|更新于2025-12-10|力扣日常 | LeetcodeDaily

|总字数:211|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个一维数组，当作一堆石头重量，每次选两个最重的碰，将两个石头之差放回去，求最后剩下的一个石头重量（没有就0）

思路分享

这种多次求最值的，用堆，只是要记得，python的 heapify 默认最小堆，所以数字先做负数处理再堆化。

https://leetcode.cn/problems/last-stone-weight/solutions/540130/zui-hou-yi-kuai-shi-tou-de-zhong-liang-b-xgsx/

代码解答（强烈建议自行解答后再看）

参考题解

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        for i in range(len(stones)):
            stones[i] = -stones[i]
        heapify(stones)
        while stones and len(stones) > 1:
            # print(stones)
            x = heappop(stones)
            y = heappop(stones)
            d = abs(x-y)
            if d != 0:
                heappush(stones, -d)
        return 0 if not stones or len(stones)==0 else -heappop(stones)

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/20cfa86.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

相关推荐

【Leetcode Daily】2558从数量最多的堆取走礼物

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个数组，并重复 k 次找其中最大的数字平方再放回去，返回最后数组的数值和。思路分享对于这种找最大/最小的情况，可以考虑堆。堆会自然维护堆顶为所有元素的最小或者最大，并且在去除这个最值后，也能很方便地提取出下一个最值。那有人可能就问了，之前学的单调栈和单调队列不也能方便地取最值吗，为什么不用？原因是单调栈和单调队列的维护效率不及堆，在本题，提取的最值处理后又要放回去，提取是方便，但放回去的最坏情况是O(n)，即从最大值变最小值。 https://leetcode.cn/problems/take-gifts-from-the-richest-pile/solutions/2501655/yuan-di-dui-hua-o1-kong-jian-fu-ti-dan-p-fzdh/ 代码解答（强烈建议自行解答后再看）参考题解 1234567891011class Solution: def pickGifts(self, gifts: List[int], k: int) ->...

【Leetcode Daily】295数据流的中位数

题目浅析想查看原题可以点击题目链接。简单地说，就是在给数组增添数字的过程中，可能需要随时输出当前的中位数。思路分享构建大小堆，也就是一个大顶堆和一个小顶堆，前者相当于当前数字的左侧，后者相当于右侧，这样就能随时得到左边最大和右边最小的数值，也就方便计算中位数了。 https://leetcode.cn/problems/find-median-from-data-stream/solutions/3015873/ru-he-zi-ran-yin-ru-da-xiao-dui-jian-ji-4v22k/ 具体而言，需要保证两点，第一是优先把数字放左侧，随后如果左侧的数字更多，再放右边；第二保证左侧的所有数字都小于右侧，所以如果要加到左侧的数字，可以先加到右侧，再从右侧获取最小的数字加到左侧。代码解答（强烈建议自行解答后再看）参考题解 1234567891011121314151617181920212223class MedianFinder: def __init__(self): self.left = [] ...

【Leetcode Daily】480滑动窗口中位数

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个数组和一个窗口大小 k，现在规定这个窗口从数组最左侧移到最右侧，求每个窗口的中位数。思路分享比起【Leetcode Daily】295数据流的中位数，本题多加了需要删除的功能，但是对于堆而言，想要找到其中的值再删除，相当于重建，复杂度比较高。这里就可以引入“懒删除堆”，顾名思义，这个堆删除值不会立刻删除，而是先记录下来，在做入堆，取堆顶等操作的同时，检查堆顶是否为需要删除的值，是则直接弹出堆顶，不是则照常操作。 https://leetcode.cn/problems/sliding-window-median/solutions/3628827/295-ti-lan-shan-chu-dui-pythonjavacgojsr-66ch/ 注意，对于大小堆这种写法引入删除后，注意保持 left 的 size 与 right 相等或者多...

【Leetcode Daily】3264K次乘运算后的最终数组I

题目浅析想查看原题可以点击题目链接。简单地说，就是给一维数组，k 和 m，k 次从数组中找到最小的值，原地乘 m，求最终的数组。思路分享本题比较重要的一点是，题目要求是在原地进行乘法操作，所以如果要用堆处理，需要同时保存下标信息。接下来就好说了，先做出保存下标信息的堆，然后不断取出小值乘 m 放回，直到达到 k 次。代码解答（强烈建议自行解答后再看）参考题解 1234567891011class Solution: def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]: rec = [(x, i) for i, x in enumerate(nums)] heapify(rec) for _ in range(k): new_num = rec[0][0] * multiplier new_index = rec[0][1] ...

【Leetcode Daily】2336无限集中的最小数字

题目浅析想查看原题可以点击题目链接。简单地说，就是要实现一个数据结构，这个结构初始是一个正整数集合，要求能返回集合中的最小值，并随时往集合里加正整数。思路分享返回最小值，可以用堆来维护，至于堆是维护新加的，还是已有的，就看具体实现方式。但都需要思考如何去重，避免重复添加。官方题解提到了 SortedSet，可以在完成堆的任务的同时，高效去重。就不需要像参考题解这样，又用堆，也用 Set 了。 https://leetcode.cn/problems/smallest-number-in-infinite-set/solutions/2542156/wu-xian-ji-zhong-de-zui-xiao-shu-zi-by-l-5mfr/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415161718192021222324252627282930class SmallestInfiniteSet: def __init__(self): self.heap = [1] ...

【Leetcode Daily】2530执行K次操作后的最大分数

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个数组和一个整数 k，现在从数组中取一个数算分数，然后将这个数除三并向上取整放回去，求执行 k 次后能获取的最大分数。思路分享频繁地求一个数组的最大值，那必须是堆出场。由于默认小顶堆，所以把数组的值取反再建堆就是大顶堆了。至于向上取整，在负数的情况下， python 直接整除就算取整了，如果不放心，可以调用 floor 函数，在负数时向下取整就是普通的向上取整。 https://leetcode.cn/problems/maximal-score-after-applying-k-operations/solutions/2487446/o1-kong-jian-zuo-fa-pythonjavacgojsrust-ztx6f/ 代码解答（强烈建议自行解答后再看）参考题解 1234567891011121314151617class Solution: def maxKelements(self, nums: List[int], k: int) -> int: ans =...

数据加载中