移除石子使总数最小 图解题解
这道题到底在问什么
- 输入
- piles = [5,4,9], k = 2
- 输出
- 12 先砍 9 得 5,再砍 5 得 3,剩 [3,4,5] 共 12
- 输入
- piles = [8,5,12,6,4,7], k = 6
- 输出
- 21 本节演示数据,六次都砍当前最大堆
最优解：一步一步想明白
- 3记牢这一句:每次都砍当前最大的堆。因为一次拿走的是数量的一半、向下取整,堆越大拿走越多,砍最大堆是每一步的最优选择,合起来就是全局最优。用大根堆来回取最大、放回最快。下面先把六堆石子整理成一个大根堆。
- 4先把六堆石子原样放进堆里,按层序排开就是 8、5、12、6、4、7。注意这时堆顶是 8,可真正最大的 12 还窝在下面。大根堆要求每个父节点都不小于它的两个孩子,现在还不满足,得从最底层往上把它整理一遍。
- 5层序里最后一个有孩子的节点是 12,它和孩子 7 已经满足父不小于子,不用动。继续往前,5 比它的孩子小,就和较大的那个孩子交换位置,让大的往上走、小的往下沉。交换之后这一小片就满足父不小于子了。
- 6继续往前,轮到堆顶的 8。它的两个孩子里有更大的,把最大的 12 换上来当堆顶,8 沉下去。这样一路下沉,最大的值就浮到了堆顶。
- 7整理完成,现在这是一棵合格的大根堆:每个父节点都不小于孩子,堆顶 12 就是六堆里最多的一堆。接下来就重复六次同一个动作:看堆顶、砍掉一半、把剩下的放回去下沉。每一次都在砍当前最大堆。
- 8开始第 1 次操作。堆顶永远是当前最大的一堆,现在是 12。按贪心,这一刀就砍它。砍掉的是它的一半、向下取整,也就是 floor(12 除以 2) 等于 6 颗。砍完这堆会剩下 6 颗。
- 9动手砍。堆顶从 12 减去 6,变成 6 颗,总数一下从上一步降到 36。可是堆顶被改小之后,它可能比孩子还小了,大根堆的规矩暂时被破坏。所以下一步得让它下沉,把新的最大值重新顶上来。
- 10让 6 下沉:它比孩子小,就和较大的孩子换,一路换到不再小于孩子为止。这样藏在下面的最大值 8 就重新浮到堆顶。一次操作到此收工,总数是 36。
- 11开始第 2 次操作。堆顶永远是当前最大的一堆,现在是 8。按贪心,这一刀就砍它。砍掉的是它的一半、向下取整,也就是 floor(8 除以 2) 等于 4 颗。砍完这堆会剩下 4 颗。
- 12动手砍。堆顶从 8 减去 4,变成 4 颗,总数一下从上一步降到 32。可是堆顶被改小之后,它可能比孩子还小了,大根堆的规矩暂时被破坏。所以下一步得让它下沉,把新的最大值重新顶上来。
- 13让 4 下沉:它比孩子小,就和较大的孩子换,一路换到不再小于孩子为止。这样藏在下面的最大值 7 就重新浮到堆顶。一次操作到此收工,总数是 32。
- 14开始第 3 次操作。堆顶永远是当前最大的一堆,现在是 7。按贪心,这一刀就砍它。砍掉的是它的一半、向下取整,也就是 floor(7 除以 2) 等于 3 颗。砍完这堆会剩下 4 颗。
- 15动手砍。堆顶从 7 减去 3,变成 4 颗,总数一下从上一步降到 29。可是堆顶被改小之后,它可能比孩子还小了,大根堆的规矩暂时被破坏。所以下一步得让它下沉,把新的最大值重新顶上来。
- 16让 4 下沉:它比孩子小,就和较大的孩子换,一路换到不再小于孩子为止。这样藏在下面的最大值 6 就重新浮到堆顶。一次操作到此收工,总数是 29。
- 17开始第 4 次操作。堆顶永远是当前最大的一堆,现在是 6。按贪心,这一刀就砍它。砍掉的是它的一半、向下取整,也就是 floor(6 除以 2) 等于 3 颗。砍完这堆会剩下 3 颗。
- 18动手砍。堆顶从 6 减去 3,变成 3 颗,总数一下从上一步降到 26。可是堆顶被改小之后,它可能比孩子还小了,大根堆的规矩暂时被破坏。所以下一步得让它下沉,把新的最大值重新顶上来。
- 19让 3 下沉:它比孩子小,就和较大的孩子换,一路换到不再小于孩子为止。这样藏在下面的最大值 6 就重新浮到堆顶。一次操作到此收工,总数是 26。
- 20开始第 5 次操作。堆顶永远是当前最大的一堆,现在是 6。按贪心,这一刀就砍它。砍掉的是它的一半、向下取整,也就是 floor(6 除以 2) 等于 3 颗。砍完这堆会剩下 3 颗。
- 21动手砍。堆顶从 6 减去 3,变成 3 颗,总数一下从上一步降到 23。可是堆顶被改小之后,它可能比孩子还小了,大根堆的规矩暂时被破坏。所以下一步得让它下沉,把新的最大值重新顶上来。
- 22让 3 下沉:它比孩子小,就和较大的孩子换,一路换到不再小于孩子为止。这样藏在下面的最大值 5 就重新浮到堆顶。一次操作到此收工,总数是 23。
- 23开始第 6 次操作。堆顶永远是当前最大的一堆,现在是 5。按贪心,这一刀就砍它。砍掉的是它的一半、向下取整,也就是 floor(5 除以 2) 等于 2 颗。砍完这堆会剩下 3 颗。
- 24动手砍。堆顶从 5 减去 2,变成 3 颗,总数一下从上一步降到 21。可是堆顶被改小之后,它可能比孩子还小了,大根堆的规矩暂时被破坏。所以下一步得让它下沉,把新的最大值重新顶上来。
- 25让 3 下沉:它比孩子小,就和较大的孩子换,一路换到不再小于孩子为止。这样藏在下面的最大值 4 就重新浮到堆顶。一次操作到此收工,总数是 21。
- 26六次操作全部做完,堆里现在是 4、4、4、3、3、3。把它们加起来就是剩下的最小石子总数 21。回头看,我们从头到尾只做了一件事:每次都砍当前最大的那一堆,所以拿走的石子始终最多,剩下的自然最少。
⚠️ 容易写错的地方
✗ 错：每次都排一遍序找最大堆
✓ 对：用大根堆,取堆顶就是最大
每轮重新排序是 O(n log n),乘上 k 轮会退化到 O(k n log n) 容易超时;堆取最大只要 O(log n)
✗ 错：把砍后剩下的算成 floor(x/2)
✓ 对：剩下的是 x 减 floor(x/2)
移除的才是 floor(x/2),剩下的是另一半、向上取整。奇数堆比如 5,移除 2 剩 3,别把剩下也当成 2
✗ 错：Python 直接用 heapq 当大根堆
✓ 对：取相反数放进小根堆再取回
heapq 只有小根堆,堆顶是最小值。要拿最大值得把数取负,让最小的负数对应最大的正数,取出后再变回来
✗ 错：固定盯着某一堆一直砍
✓ 对：每一步都重新挑当前最大堆
砍半的收益随堆的大小递增,某堆被砍小后可能已不是最大,继续砍它拿走的反而变少,得让最大的那堆优先
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int minStoneSum(vector<int>& piles, int k) {
priority_queue<int> pq;
for (int x : piles) {
pq.push(x);
}
while (k--) {
int x = pq.top();
pq.pop();
pq.push(x - x / 2);
}
int ans = 0;
while (!pq.empty()) {
ans += pq.top();
pq.pop();
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int minStoneSum(int[] piles, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
for (int x : piles) {
pq.offer(x);
}
while (k-- > 0) {
int x = pq.poll();
pq.offer(x - x / 2);
}
int ans = 0;
while (!pq.isEmpty()) {
ans += pq.poll();
}
return ans;
}
}复杂度
时间
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 / Java / C++ 跟着练。
面试官可能追问
这题为什么能用贪心,正确性怎么说明?+
目标是 k 次拿走的石子总数最多。每次操作在一堆上拿走 floor(x/2),这个收益只跟被选堆的当前大小有关、随大小单调不减,而且各堆之间互不影响。所以每一步选当前最大的堆砍,单步收益最大;由于选择不会互相牵制,逐步最大自然拼出总量最大,贪心成立。
为什么用堆,不用排序?+
每次要拿当前最大值,砍完又要把改小的值放回去继续参与后面的比较。若每轮重新排序是 O(n log n) 乘 k 轮,太慢。大根堆取最大是 O(1)、弹出与插入各 O(log n),k 次总共 O(n 加 k log n),把反复找最大这件事做到了最快。
Python 没有大根堆怎么办?+
heapq 只提供小根堆,堆顶是最小值。常用技巧是把每个数取相反数入堆,这样最小的负数对应原来最大的正数,取出堆顶取负就还原成最大值。砍半后把新值取负放回,可以用 heapreplace 一步完成弹出加压入。C plus plus 和 Java 有现成的大根堆或反向比较器,就不用这个转换。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 移除石子使总数最小 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。