执行 K 次操作后的最大分数【LC2530】
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。
在一步 操作 中：
选出一个满足 0 <= i < nums.length 的下标 i ，
将你的 分数 增加 nums[i] ，并且
将 nums[i] 替换为 ceil(nums[i] / 3) 。
返回在 恰好 执行 k 次操作后，你可能获得的最大分数。
向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。
学到了
大顶堆+贪心
- 思路
- 每次操作尽量选择数组中的最大值，以获得最大分数
- 借助大顶堆存储数组元素，那么堆顶元素为每次操作的元素，每次操作完成后将ceil(num/3)放入堆中，向上取整的实现有以下三种
- 调用API：
Math.ceil(num/3.0) - 判断余数是否为0：
num / 3 + (num % 3 == 0 ? 0 : 1) - 加2后再进行整除：
(num + 2) / 3
- 实现
class Solution { public long maxKelements(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1); long res = 0L; for (int num : nums){ pq.add(num); } for (int i = 0; i < k; i++){ int num = pq.poll(); res += num; // pq.add(num / 3 + (num % 3 == 0 ? 0 : 1)); pq.add((num + 2) / 3); pq.add((int)Math.ceil(num / 3.0)); } return res; } }
复杂度
时间复杂度：O ( n + k l o g n )
空间复杂度：O ( n )
实现
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 的右儿子比 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; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/maximal-score-after-applying-k-operations/solutions/2487446/o1-kong-jian-zuo-fa-pythonjavacgojsrust-ztx6f/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
时间复杂度：O ( n + k l o g n )
空间复杂度：O ( 1 )
