LeetCode 题解工作台
移除石子使总数最小
给你一个整数数组 piles ，数组 下标从 0 开始 ，其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ，请你执行下述操作 恰好 k 次： 选出任一石子堆 piles[i] ，并从中 移除 floor(piles[i] / 2) 颗石子。 注意： 你可以对 同一堆 石子…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
根据题目描述，为了使得剩下的石子总数最小，我们需要尽可能多地移除石子堆中的石子。因此，每次应该选择数量最多的石子堆进行移除。 我们创建一个优先队列（大根堆） ，用于存储石子堆的数量。初始时，将所有石子堆的数量加入优先队列。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个整数数组 piles ，数组 下标从 0 开始 ，其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ，请你执行下述操作 恰好 k 次：
- 选出任一石子堆
piles[i]，并从中 移除floor(piles[i] / 2)颗石子。
注意：你可以对 同一堆 石子多次执行此操作。
返回执行 k 次操作后，剩下石子的 最小 总数。
floor(x) 为 小于 或 等于 x 的 最大 整数。（即，对 x 向下取整）。
示例 1：
输入：piles = [5,4,9], k = 2 输出：12 解释：可能的执行情景如下： - 对第 2 堆石子执行移除操作，石子分布情况变成 [5,4,5] 。 - 对第 0 堆石子执行移除操作，石子分布情况变成 [3,4,5] 。 剩下石子的总数为 12 。
示例 2：
输入：piles = [4,3,6,7], k = 3 输出：12 解释：可能的执行情景如下： - 对第 2 堆石子执行移除操作，石子分布情况变成 [4,3,3,7] 。 - 对第 3 堆石子执行移除操作，石子分布情况变成 [4,3,3,4] 。 - 对第 0 堆石子执行移除操作，石子分布情况变成 [2,3,3,4] 。 剩下石子的总数为 12 。
提示：
1 <= piles.length <= 1051 <= piles[i] <= 1041 <= k <= 105
解题思路
方法一：贪心 + 优先队列（大根堆）
根据题目描述，为了使得剩下的石子总数最小，我们需要尽可能多地移除石子堆中的石子。因此，每次应该选择数量最多的石子堆进行移除。
我们创建一个优先队列（大根堆） ，用于存储石子堆的数量。初始时，将所有石子堆的数量加入优先队列。
接下来，我们进行 次操作。在每一次操作中，我们取出优先队列的堆顶元素 ，将 减半后重新加入优先队列。
在进行了 次操作后，优先队列中所有元素的和即为答案。
时间复杂度 ，空间复杂度 。其中 是数组 piles 的长度。
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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + k log n), where n is the number of piles and k is the number of operations, due to heap operations each step. Space complexity is O(n) for storing the heap. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you consistently selecting the pile with the maximum stones each operation?
- question_mark
Do you validate that the total reduces optimally after each step?
- question_mark
Can your approach handle large piles arrays efficiently without scanning all piles every time?
常见陷阱
外企场景- error
Not using a heap and scanning the array every operation leads to TLE for large inputs.
- error
Incorrectly computing floor division, causing off-by-one errors in stone removal.
- error
Failing to handle repeated operations on the same pile, which violates the greedy invariant.
进阶变体
外企场景- arrow_right_alt
Instead of floor division, remove a fixed number of stones each operation and minimize total.
- arrow_right_alt
Perform operations only on piles above a certain threshold, adding a conditional greedy selection.
- arrow_right_alt
Maximize the total stones removed instead of minimizing the remaining total, using similar heap logic.