Medium

题目描述

给你一个下标从 0 开始的整数数组 piles，其中 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 <= 10⁵
  • 1 <= piles[i] <= 10⁴
  • 1 <= k <= 10⁵

解题思路

这道题要求我们在 k 次操作中最小化剩余石子总数，关键在于每次都要选择能带来最大收益的操作。

核心思路：贪心算法 每次操作移除 floor(pile[i] / 2) 颗石子，显然石子数量越多的堆，移除的石子数也越多。因此贪心策略是：每次都选择当前石子数量最多的堆进行操作。

算法步骤：

  1. 使用最大堆（优先队列）来维护所有石堆，确保能快速找到最大值
  2. 进行 k 次操作，每次：
    • 取出堆顶元素（最大石堆）
    • 计算移除的石子数：removed = pile / 2
    • 计算剩余石子数：remaining = pile - removed
    • 将剩余石子数重新放入堆中
  3. 最后计算堆中所有元素的和

时间复杂度分析：

  • 建堆：O(n)
  • k 次操作，每次堆操作：O(log n)
  • 总时间复杂度：O(n + k log n)

空间复杂度： O(n) 用于存储优先队列

这种贪心策略是正确的，因为每次选择最大堆能保证当前操作的收益最大，从而使总体收益最大。

代码实现

class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        priority_queue<int> maxHeap(piles.begin(), piles.end());
        
        for (int i = 0; i < k; i++) {
            int maxPile = maxHeap.top();
            maxHeap.pop();
            maxHeap.push(maxPile - maxPile / 2);
        }
        
        int total = 0;
        while (!maxHeap.empty()) {
            total += maxHeap.top();
            maxHeap.pop();
        }
        
        return total;
    }
};

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        # Python的heapq是最小堆，所以存入负值来模拟最大堆
        max_heap = [-pile for pile in piles]
        heapq.heapify(max_heap)
        
        for _ in range(k):
            max_pile = -heapq.heappop(max_heap)
            remaining = max_pile - max_pile // 2
            heapq.heappush(max_heap, -remaining)
        
        return -sum(max_heap)

public class Solution {
    public int MinStoneSum(int[] piles, int k) {
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        
        foreach (int pile in piles) {
            maxHeap.Enqueue(pile, pile);
        }
        
        for (int i = 0; i < k; i++) {
            int maxPile = maxHeap.Dequeue();
            int remaining = maxPile - maxPile / 2;
            maxHeap.Enqueue(remaining, remaining);
        }
        
        int total = 0;
        while (maxHeap.Count > 0) {
            total += maxHeap.Dequeue();
        }
        
        return total;
    }
}

var minStoneSum = function(piles, k) {
    // JavaScript没有内置优先队列，使用数组模拟最大堆
    const maxHeap = [...piles];
    maxHeap.sort((a, b) => b - a);
    
    for (let i = 0; i < k; i++) {
        const maxPile = maxHeap.shift();
        const remaining = maxPile - Math.floor(maxPile / 2);
        
        // 插入到正确位置保持有序
        let insertIndex = 0;
        while (insertIndex < maxHeap.length && maxHeap[insertIndex] > remaining) {
            insertIndex++;
        }
        maxHeap.splice(insertIndex, 0, remaining);
    }
    
    return maxHeap.reduce((sum, pile) => sum + pile, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值说明
时间复杂度O(n + k log n)建堆 O(n)，k 次堆操作每次 O(log n)
空间复杂度O(n)优先队列存储所有石堆

相关题目