LeetCode 题解工作台
超过阈值的最少操作数 II
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 你可以对 nums 执行一些操作，在一次操作中，你可以： 选择 nums 中 最小 的两个整数 x 和 y 。 将 x 和 y 从 nums 中删除。 将 min(x, y) * 2 + max(x, y) 添加到数组中的任意位置。 …
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 堆
答案摘要
我们可以使用优先队列（小根堆）来模拟这个过程。 具体地，我们先将数组中的元素加入优先队列 中。然后我们不断地从优先队列中取出两个最小的元素 和 ，将 $\min(x, y) \times 2 + \max(x, y)$ 放回优先队列中。每次操作后，我们将操作次数加一。当队列中的元素个数小于 或者队列中的最小元素大于等于 时，我们停止操作。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 堆 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
你可以对 nums 执行一些操作，在一次操作中，你可以：
- 选择
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]。
此时，nums 中的所有元素都大于等于 20 ，所以我们停止操作。
可以证明使数组中所有元素都大于等于 20 需要的最少操作次数为 4 。
提示：
2 <= nums.length <= 2 * 1051 <= nums[i] <= 1091 <= k <= 109- 输入保证答案一定存在，也就是说，在进行某些次数的操作后，数组中所有元素都大于等于
k。
解题思路
方法一：优先队列（小根堆）
我们可以使用优先队列（小根堆）来模拟这个过程。
具体地，我们先将数组中的元素加入优先队列 中。然后我们不断地从优先队列中取出两个最小的元素 和 ，将 放回优先队列中。每次操作后，我们将操作次数加一。当队列中的元素个数小于 或者队列中的最小元素大于等于 时，我们停止操作。
时间复杂度 ，空间复杂度 。其中 为数组长度。
class Solution:
def minOperations(self, nums: List[int], k: int) -> int:
heapify(nums)
ans = 0
while len(nums) > 1 and nums[0] < k:
x, y = heappop(nums), heappop(nums)
heappush(nums, x * 2 + y)
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N log N) because each heap operation (pop and push) costs O(log N) and we perform up to N operations. Space complexity is O(N) to store all array elements in the heap. |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Does the candidate correctly identify the need for a min-heap to track smallest elements?
- question_mark
Can they simulate operations efficiently without iterating over the entire array each time?
- question_mark
Do they consider edge cases where repeated operations barely meet the threshold?
常见陷阱
外企场景- error
Trying to sort the array repeatedly instead of using a heap, which increases time complexity.
- error
Failing to check the array length before performing an operation, leading to invalid operations.
- error
Incorrectly combining elements or forgetting to increment the operation counter properly.
进阶变体
外企场景- arrow_right_alt
Change the operation formula to include multiplication instead of addition and test heap behavior.
- arrow_right_alt
Require that only a subset of the array must exceed k instead of all elements.
- arrow_right_alt
Apply the same heap simulation approach on a dynamic stream of elements rather than a static array.