LeetCode 2530. 执行 K 次操作后的最大分数【贪心,原地堆化】1386

贪心,原地堆化】1386"/>

LeetCode 2530. 执行 K 次操作后的最大分数【贪心,原地堆化】1386

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。

在一步 操作 中：

1. 选出一个满足 0 <= i < nums.length 的下标 i ，
2. 将你的 分数 增加 nums[i] ，并且
3. 将 nums[i] 替换为 ceil(nums[i] / 3) 。

返回在 恰好 执行 k 次操作后，你可能获得的最大分数。

向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。

示例 1：

输入：nums = [10,10,10,10,10], k = 5
输出：50
解释：对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。

示例 2：

输入：nums = [1,10,3,3,3], k = 3
输出：17
解释：可以执行下述操作：
第 1 步操作：选中 i = 1 ，nums 变为 [1,4,3,3,3] 。分数增加 10 。
第 2 步操作：选中 i = 1 ，nums 变为 [1,2,3,3,3] 。分数增加 4 。
第 3 步操作：选中 i = 2 ，nums 变为 [1,1,1,3,3] 。分数增加 3 。
最后分数是 10 + 4 + 3 = 17 。

提示：

• 1 <= nums.length, k <= 10^5
• 1 <= nums[i] <= 10^9

解法 贪心+原地堆化

用一个最大堆模拟。循环 k k k 次，每次循环把堆顶加入答案，然后把堆顶 t o p top top 更新为 ceil(top/3) 。

原地堆化（heapify）可以做到 O ( 1 ) O(1) O(1) 的空间复杂度。部分语言用的标准库自带的堆化函数，具体实现可以看下面的 Java 代码。

class Solution {
public:long long maxKelements(vector<int>& nums, int k) {make_heap(nums.begin(), nums.end()); // 原地堆化(最大堆)long long ans = 0;while (k--) {pop_heap(nums.begin(), nums.end()); // 把堆顶移到末尾ans += nums.back();nums.back() = (nums.back() + 2) / 3;push_heap(nums.begin(), nums.end()); // 把末尾元素入堆}return ans;}
};

class Solution {public long maxKelements(int[] nums, int k) {heapify(nums); // 原地堆化(最大堆)long ans = 0;while (k-- > 0) {ans += nums[0]; // 堆顶nums[0] = (nums[0] + 2) / 3;sink(nums, 0); // 堆化(只要把nums[0]下沉即可)}return ans;}// 原地堆化（最大堆）// 堆化可以保证 h[0] 是堆顶元素，且 h[i] >= max(h[2*i+1], h[2*i+2])private void heapify(int[] h) {// 下标 >= h.length / 2 的元素是二叉树的叶子，无需下沉// 倒着遍历，从而保证 i 的左右子树一定是堆，那么 sink(h, i) 就可以把左右子树合并成一个堆for (int i = h.length / 2 - 1; i >= 0; i--)sink(h, i);}// 把 h[i] 不断下沉，直到 i 的左右儿子都 <= h[i]private void sink(int[] h, int i) {int n = h.length;while (2 * i + 1 < n) {int j = 2 * i + 1; // i的左儿子if (j + 1 < n && h[j + 1] > h[j]) // i的右儿子比左儿子大++j;if (h[j] <= h[i]) // 说明i的左右儿子都<=h[i],停止下沉break;swap(h, i, j); // 下沉i = j;}}// 交换h[i]和h[j]private void swap(int[] h, int i, int j) {int tmp = h[i];h[i] = h[j];h[j] = tmp;}
}

复杂度分析：

• 时间复杂度： O ( n + k log ⁡ n ) \mathcal{O}(n + k\log n) O(n+klogn) ，其中 n n n 为 nums \textit{nums} nums 的长度。把 nums \textit{nums} nums 堆化需要 O ( n ) \mathcal{O}(n) O(n) 时间。
• 空间复杂度： O ( 1 ) \mathcal{O}(1) O(1) 。