3066.超过阈值的最少操作数II

🎯 问题描述（来源于LeetCode）

描述：
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
你可以对 nums 执行一些操作，在一次操作中，你可以：

  • 选择 nums 中 最小 的两个整数 x 和 y 。
  • 将 x 和 y 从 nums 中删除。
  • 将 min(x, y) * 2 + max(x, y) 添加到数组中的任意位置。
    注意，只有当 nums 至少包含两个元素时，你才可以执行以上操作。

你需要使数组中的所有元素都 大于或等于 k ，请你返回需要的 最少 操作次数。

说明：

  • 为了用最少的操作次数让所有元素达标，我们的贪心策略是：每次都挑选当前数组中最小的两个数进行合并。这样能最快地把较小的数值“消灭”掉，转化为更大的数值。

  • 示例：

    • 示例 1：
      1
      2
      3
      4
      5
      6
      输入：nums = [2,11,10,1,3], k = 10
      输出：2
      解释：
      第1次操作：选出 1 和 2，合并为 1*2+2=4，数组变为 [3,4,10,11]。
      第2次操作：选出 3 和 4，合并为 3*2+4=10，数组变为 [10,10,11]。
      此时所有元素都 >= 10，共操作 2 次。
    • 示例 2：
      1
      2
      3
      输入：nums = [1,1,2,4,9], k = 20
      输出：4
      解释：经过多次合并后，最终所有元素都会变得足够大。

💻 解题思路

思路1：贪心 + 最小堆

代码实现

import heapq
from typing import List
class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        ans = 0
        while len(nums)>1:
            x,y = heapq.heappop(nums),heapq.heappop(nums)
            if x >= k:
                return ans
            new_val = x*2+y
            heapq.heappush(nums,new_val)
            ans += 1
        return ans

📊 性能分析

  • 时间复杂度：O(nlog⁡n)O(n \log n)。建堆需要 O(n)O(n)，每次操作涉及两次弹出和一次推入，单次操作复杂度为 O(log⁡n)O(\log n)，最多进行 nn 次操作。
  • 空间复杂度：O(1)O(1)（如果不计算输入数组的修改）或 O(n)O(n)（取决于堆的实现方式）。

💡 思考

这道题的核心在于贪心策略：每次合并最小的两个数，可以最大程度地保留较大的数，同时以最快的速度提升小数值。使用最小堆（优先队列）可以让我们在 O(1)O(1) 的时间内获取最小值，并在 O(log⁡n) 的时间内完成数据的更新，是处理此类“反复取极值”问题的最优解。