LeetCode移除石子问题中heap replace是否比先pop再push效率更高？

数据老陈

2026-10-8

LeetCode《移除石子使总数最小》两种堆解法效率差异分析

超时版本解法

from math import floor
import heapq
def minStoneSum(piles, k: int) -> int:
    while k > 0:
        heapq._heapify_max(piles)
        max_pile = heapq._heappop_max(piles)
        remove_stones = floor(max_pile / 2)
        replacement = max_pile- remove_stones
        heapq.heappush(piles,replacement)
        k -= 1

    return sum(piles)

print(minStoneSum([5,4,9], 2))

全量用例通过的优化解法

from typing import List
import heapq
def minStoneSum(self, piles: List[int], k: int) -> int:
        pq = [-x for x in piles]
        heapq.heapify(pq)
        for _ in range(k): 
            heapq.heapreplace(pq,pq[0]//2)
        return -sum(pq)

效率差异核心原因

重复堆化是超时的核心诱因：你的代码在每次循环迭代时都执行了heapq._heapify_max(piles)操作，堆化的时间复杂度为O(n)，n为石子堆的数量。如果测试用例中k的取值达到1e4甚至更高的量级，整体时间复杂度会劣化到O(kn)，完全超出时间限制。而优化解法仅在初始化阶段执行1次O(n)的堆化，后续所有操作的复杂度都是O(logn)，整体复杂度为O(n + klogn)，符合题目时间要求。
堆操作的实现效率差异：你提到的「弹出再插入」比「直接替换堆顶」效率更低确实是次要原因。heapreplace是弹出堆顶+插入新元素的原子优化操作，内部逻辑比分开调用_heappop_max + heappush的开销更小。另外你使用的_heapify_max、_heappop_max都是heapq模块的私有方法，本身没有公开的小顶堆方法实现高效稳定，优化解法通过存负数模拟大顶堆，调用的都是heapq原生优化过的公开小顶堆接口，性能更好。
冗余操作的微小开销：你额外导入math模块调用floor计算半值，Python中整数除法//本身就是向下取整，不需要额外的函数调用开销，不过这部分不是超时的主要原因。