原地建堆，LeetCode 1962. 移除石子使总数最小

一、题目

1、题目描述

给你一个整数数组?piles?，数组?下标从 0 开始?，其中?piles[i]?表示第?i?堆石子中的石子数量。另给你一个整数?k?，请你执行下述操作?恰好?k?次：

• 选出任一石子堆?piles[i]?，并从中?移除?floor(piles[i] / 2)?颗石子。

注意：你可以对?同一堆?石子多次执行此操作。

返回执行?k?次操作后，剩下石子的?最小?总数。

floor(x)?为?小于?或?等于?x?的?最大?整数。（即，对?x?向下取整）。

2、接口描述

?

class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {

    }
};

3、原题链接

1962. 移除石子使总数最小

---

二、解题报告

1、思路分析

显然我们每次都移除数目最多的那一堆，最后一定能够满足剩下的最小，每次找到最大数目的石子堆我们可以选择使用大根堆来实现。

我们如果将数组元素都插入堆中，那么需要O(nlogn)的时间复杂度和O(n)的空间复杂度，我们可以选择直接原地建堆，即在原数组上建堆，采用向下调整算法自下而上建堆可以达到O(n)的时间复杂度建堆，关于堆的两种构建算法以及时间复杂度证明，见：堆/二叉堆详解[C/C++]-CSDN博客

然后执行k次操作，如果堆顶元素为1，那么此时无法再拿出元素，我们直接退出循环即可

2、复杂度

时间复杂度：O(n?+ klogn)?空间复杂度：O(1)

3、代码详解

?C++版本

class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        //原地堆化默认大根堆
        make_heap(piles.begin() , piles.end());
        while(k-- && (piles[0] ^ 1)){
            pop_heap(piles.begin() , piles.end());//弹出堆顶到末尾
            piles.back() -= piles.back() / 2;
            push_heap(piles.begin() , piles.end());//向上调整插入末尾元素到堆
        }
        return accumulate(piles.begin() , piles.end() , 0);
    }
};

python3版本

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        for i in range(len(piles)):
            piles[i] *= -1
        heapify(piles)
        while k and (piles[0] ^ 1):
            heapreplace(piles , piles[0] // 2) # 负数向下取整的绝对值和正数向上取整绝对值一样
            k -= 1
        return -sum(piles)