[LeetCode] 每日一题 3066. 超过阈值的最少操作数 II
题目链接
题目描述
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一次操作中，你将执行：
选择
nums中最小的两个整数x和y。将
x和y从nums中删除。将
min(x, y) * 2 + max(x, y)添加到数组中的任意位置。
注意，只有当 nums 至少包含两个元素时，你才可以执行以上操作。
你需要使数组中的所有元素都大于或等于 k ，请你返回需要的 最少 操作次数。
示例输入
示例 1
输入：nums = [2,11,10,1,3], k = 10
输出：2
解释：第一次操作中，我们删除元素 1 和 2 ，然后添加 1 * 2 + 2 到 nums 中，nums 变为 [4, 11, 10, 3] 。
第二次操作中，我们删除元素 3 和 4 ，然后添加 3 * 2 + 4 到 nums 中，nums 变为 [10, 11, 10] 。
此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。
使数组中所有元素都大于等于 10 需要的最少操作次数为 2 。示例 2
输入：nums = [1,1,2,4,9], k = 20
输出：4
解释：第一次操作后，nums 变为 [2, 4, 9, 3] 。
第二次操作后，nums 变为 [7, 4, 9] 。
第三次操作后，nums 变为 [15, 9] 。
第四次操作后，nums 变为 [33] 。
此时，数组中的所有元素都大于等于 20 ，所以我们停止操作。
使数组中所有元素都大于等于 20 需要的最少操作次数为 4 。提示
2 <= nums.length <= 2 * 10^51 <= nums[i] <= 10^91 <= k <= 10^9输入保证答案一定存在，也就是说一定存在一个操作序列使数组中所有元素都大于等于
k。
解题思路
今天的这道题虽然和昨天的难度相似，实际上有一些细节值得注意，尤其是要从数组中删除最小的两个元素并进行操作。这个过程的核心思想是利用最小堆（优先队列），它能够保证我们每次操作时都能轻松找到最小的两个数
我的解法的关键是：
使用
PriorityQueue来维护最小堆，使得每次操作都能取到最小的两个元素x和y执行题目中的操作：计算
min(x, y) * 2 + max(x, y)，并将结果重新插入堆中不断执行这个操作，直到堆中的最小元素大于或等于
k
值得一提的是，在这个过程中，我最初遇到一个问题：数组的数值范围很大，nums[i] 和 k 的最大值都可以达到 10^9，因此最初我使用了 Integer 类型。结果因为数据越界导致提交失败，经过查看题目范围后，我改用了 Long 类型，避免了溢出问题
此外，虽然题目中提到“将 min(x, y) * 2 + max(x, y) 添加到数组中的任意位置”，但是由于我们是从最小堆中取出两个元素，x 必然小于 y，所以直接用 x + x + y 来简化计算，避免了额外的判断逻辑。这个优化使得代码更加简洁且高效
代码实现
class Solution {
public int minOperations(int[] nums, int k) {
PriorityQueue<Long> queue = new PriorityQueue<>();
int cnt = 0;
for (int num : nums) {
queue.offer(Long.valueOf(num));
}
while (queue.size() >= 2 && queue.peek() < k) {
cnt++;
long x = queue.poll();
long y = queue.poll();
queue.offer(x + x + y);
}
return cnt;
}
}复杂度分析
时间复杂度：
O(n log n)，其中n是数组nums的长度。每次操作从优先队列中删除两个元素并插入一个新的元素，时间复杂度为O(log n)。由于最多执行n次操作，整体时间复杂度是O(n log n)空间复杂度：
O(n)，我们使用了一个优先队列来存储所有的元素，空间复杂度为O(n)
总结
这道题虽然看起来比较简单，但处理数值范围大的问题时，我们要特别注意避免数据越界。在我自己的解决过程中，初次提交时就因为溢出错误没有通过，经过反思后选择了 Long 类型，顺利解决了问题。这也让我对题目给出的数据范围有了更加深刻的理解。在实际开发中，像这样的细节问题时常会遇到，只有细心才能避免低级错误
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。