移除石子使总数最小-LeetCode

1962.移除石子使总数最小

🎯 问题描述（来源于LeetCode）

描述：
给你一个整数数组 piles，其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k，请你执行下述操作 恰好 k 次：
选出任一石子堆 piles[i]，并从中移除 floor(piles[i] / 2) 颗石子（即向下取整）。
注意：你可以对同一堆石子多次执行此操作。
返回执行 k 次操作后，剩下石子的最小总数。

说明：

• 为了让剩下的石子总数最小，我们的贪心策略是：每次操作都应该选取当前石子数量最多的一堆来移除。

• 对最大值进行减半操作，能最大程度地减少石子总数。

• 示例：

  • 示例 1：

    输入：piles = [5,4,9], k = 2
    输出：12
    解释：
    第1次：对第2堆(9)操作，移除 floor(9/2)=4 颗，变为 [5,4,5]。
    第2次：对第0堆(5)操作，移除 floor(5/2)=2 颗，变为 [3,4,5]。
    剩下石子的总数为 3 + 4 + 5 = 12。

  • 示例 2：

    输入：piles = [4,3,6,7], k = 3
    输出：12
    解释：依次对 6, 7, 4 进行操作，最终剩下 [2,3,3,4]，总和为 12。

💻 解题思路

思路1：贪心 + 最大堆

代码实现

import heapq
from typing import List
class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        heapq.heapify_max(piles)
        while k:
            current = heapq.heappop_max(piles)
            new_val = current - current // 2
            heapq.heappush_max(piles,new_val)
            k -= 1

📊 性能分析

• 时间复杂度：$O(k \log n)$每次弹出和推入堆的操作需要 $O(\log n)$，共执行 $k$ 次。
• 空间复杂度：$O(n)$。主要为堆占用的空间。

💡 思考

这道题是典型的“反复取极值”问题。贪心策略保证了每次操作收益最大（减去的石子最多）。