题目描述
思路解析动画文字版
记牢这一句:每次都砍当前最大的堆。因为一次拿走的是数量的一半、向下取整,堆越大拿走越多,砍最大堆是每一步的最优选择,合起来就是全局最优。用大根堆来回取最大、放回最快。下面先把六堆石子整理成一个大根堆。
先把六堆石子倒进堆 · 还没整理：先把六堆石子原样放进堆里,按层序排开就是 8、5、12、6、4、7。注意这时堆顶是 8,可真正最大的 12 还窝在下面。大根堆要求每个父节点都不小于它的两个孩子,现在还不满足,得从最底层往上把它整理一遍。
整理大根堆 · 下沉位置 1：层序里最后一个有孩子的节点是 12,它和孩子 7 已经满足父不小于子,不用动。继续往前,5 比它的孩子小,就和较大的那个孩子交换位置,让大的往上走、小的往下沉。交换之后这一小片就满足父不小于子了。
整理大根堆 · 下沉位置 0：继续往前,轮到堆顶的 8。它的两个孩子里有更大的,把最大的 12 换上来当堆顶,8 沉下去。这样一路下沉,最大的值就浮到了堆顶。
大根堆建好 · 堆顶 12 就是当前最大：整理完成,现在这是一棵合格的大根堆:每个父节点都不小于孩子,堆顶 12 就是六堆里最多的一堆。接下来就重复六次同一个动作:看堆顶、砍掉一半、把剩下的放回去下沉。每一次都在砍当前最大堆。
第 1 次操作 · 看堆顶最大 = 12：开始第 1 次操作。堆顶永远是当前最大的一堆,现在是 12。按贪心,这一刀就砍它。砍掉的是它的一半、向下取整,也就是 floor(12 除以 2) 等于 6 颗。砍完这堆会剩下 6 颗。
第 1 次操作 · 砍半:12 变 6：动手砍。堆顶从 12 减去 6,变成 6 颗,总数一下从上一步降到 36。可是堆顶被改小之后,它可能比孩子还小了,大根堆的规矩暂时被破坏。所以下一步得让它下沉,把新的最大值重新顶上来。
第 1 次操作 · 下沉,新堆顶 = 8：让 6 下沉:它比孩子小,就和较大的孩子换,一路换到不再小于孩子为止。这样藏在下面的最大值 8 就重新浮到堆顶。一次操作到此收工,总数是 36。
第 2 次操作 · 看堆顶最大 = 8：开始第 2 次操作。堆顶永远是当前最大的一堆,现在是 8。按贪心,这一刀就砍它。砍掉的是它的一半、向下取整,也就是 floor(8 除以 2) 等于 4 颗。砍完这堆会剩下 4 颗。
第 2 次操作 · 砍半:8 变 4：动手砍。堆顶从 8 减去 4,变成 4 颗,总数一下从上一步降到 32。可是堆顶被改小之后,它可能比孩子还小了,大根堆的规矩暂时被破坏。所以下一步得让它下沉,把新的最大值重新顶上来。
第 2 次操作 · 下沉,新堆顶 = 7：让 4 下沉:它比孩子小,就和较大的孩子换,一路换到不再小于孩子为止。这样藏在下面的最大值 7 就重新浮到堆顶。一次操作到此收工,总数是 32。
第 3 次操作 · 看堆顶最大 = 7：开始第 3 次操作。堆顶永远是当前最大的一堆,现在是 7。按贪心,这一刀就砍它。砍掉的是它的一半、向下取整,也就是 floor(7 除以 2) 等于 3 颗。砍完这堆会剩下 4 颗。
第 3 次操作 · 砍半:7 变 4：动手砍。堆顶从 7 减去 3,变成 4 颗,总数一下从上一步降到 29。可是堆顶被改小之后,它可能比孩子还小了,大根堆的规矩暂时被破坏。所以下一步得让它下沉,把新的最大值重新顶上来。
第 3 次操作 · 下沉,新堆顶 = 6：让 4 下沉:它比孩子小,就和较大的孩子换,一路换到不再小于孩子为止。这样藏在下面的最大值 6 就重新浮到堆顶。一次操作到此收工,总数是 29。
第 4 次操作 · 看堆顶最大 = 6：开始第 4 次操作。堆顶永远是当前最大的一堆,现在是 6。按贪心,这一刀就砍它。砍掉的是它的一半、向下取整,也就是 floor(6 除以 2) 等于 3 颗。砍完这堆会剩下 3 颗。
第 4 次操作 · 砍半:6 变 3：动手砍。堆顶从 6 减去 3,变成 3 颗,总数一下从上一步降到 26。可是堆顶被改小之后,它可能比孩子还小了,大根堆的规矩暂时被破坏。所以下一步得让它下沉,把新的最大值重新顶上来。
第 4 次操作 · 下沉,新堆顶 = 6：让 3 下沉:它比孩子小,就和较大的孩子换,一路换到不再小于孩子为止。这样藏在下面的最大值 6 就重新浮到堆顶。一次操作到此收工,总数是 26。
第 5 次操作 · 看堆顶最大 = 6：开始第 5 次操作。堆顶永远是当前最大的一堆,现在是 6。按贪心,这一刀就砍它。砍掉的是它的一半、向下取整,也就是 floor(6 除以 2) 等于 3 颗。砍完这堆会剩下 3 颗。
第 5 次操作 · 砍半:6 变 3：动手砍。堆顶从 6 减去 3,变成 3 颗,总数一下从上一步降到 23。可是堆顶被改小之后,它可能比孩子还小了,大根堆的规矩暂时被破坏。所以下一步得让它下沉,把新的最大值重新顶上来。
第 5 次操作 · 下沉,新堆顶 = 5：让 3 下沉:它比孩子小,就和较大的孩子换,一路换到不再小于孩子为止。这样藏在下面的最大值 5 就重新浮到堆顶。一次操作到此收工,总数是 23。
第 6 次操作 · 看堆顶最大 = 5：开始第 6 次操作。堆顶永远是当前最大的一堆,现在是 5。按贪心,这一刀就砍它。砍掉的是它的一半、向下取整,也就是 floor(5 除以 2) 等于 2 颗。砍完这堆会剩下 3 颗。
第 6 次操作 · 砍半:5 变 3：动手砍。堆顶从 5 减去 2,变成 3 颗,总数一下从上一步降到 21。可是堆顶被改小之后,它可能比孩子还小了,大根堆的规矩暂时被破坏。所以下一步得让它下沉,把新的最大值重新顶上来。
第 6 次操作 · 下沉,新堆顶 = 4：让 3 下沉:它比孩子小,就和较大的孩子换,一路换到不再小于孩子为止。这样藏在下面的最大值 4 就重新浮到堆顶。一次操作到此收工,总数是 21。
六次砍完 · 把堆里的值全部加起来 = 21：六次操作全部做完,堆里现在是 4、4、4、3、3、3。把它们加起来就是剩下的最小石子总数 21。回头看,我们从头到尾只做了一件事:每次都砍当前最大的那一堆,所以拿走的石子始终最多,剩下的自然最少。
边界想清:堆是 1 时砍它拿不走石子、示例一得 12、示例二得 12,都靠每次砍最大验证。
面试重点:贪心正确性靠单步收益单调且互不影响、用堆取最大最快、Python 取负模拟大根堆。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def minStoneSum(self, piles: List[int], k: int) -> int: pq = [-x for x in piles] heapify(pq) for _ in range(k): heapreplace(pq, pq[0] // 2) return -sum(pq)复杂度
- 时间：O(n + k log n)，n 是堆的数量。建堆 O(n),之后每次操作要弹出堆顶再放回一个值、各做一次下沉,单次 O(log n),一共 k 次,合起来 O(n 加 k log n)
- 空间：O(n)，按峰值算。堆本身要装下全部 n 堆石子,占 O(n);下沉是原地交换,不额外开结构。Python 版另存了一份取相反数后的列表,也是 O(n) 量级
易错点
面试追问把动画讲成自己的话
追问这题为什么能用贪心,正确性怎么说明?
追问为什么用堆,不用排序?
追问Python 没有大根堆怎么办?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
构造限制重复的字符串
LeetCode 2182 · 中等 · 沿着 堆套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题