超过阈值的最少操作数 II

标签: 数组 模拟 堆（优先队列）

难度: Medium

给你一个下标从 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 * 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109
  • 输入保证答案一定存在，也就是说一定存在一个操作序列使数组中所有元素都大于等于 k 。

Submission

运行时间: 226 ms

内存: 35.2 MB

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        
        nums.sort()
        q1 = deque(nums)
        q2 = deque()
        ans = 0
        
        while q1 or q2:
            drop = [0] * 2
            for i in range(2):
                if not q2 or (q1 and q1[0] <= q2[0]):
                    drop[i] = q1.popleft()
                else:
                    drop[i] = q2.popleft()
                if drop[i] >= k:
                    break
                
            q2.append(drop[0]*2+drop[1])
            ans += 1
            if drop[0] >= k:
                ans -= 1
                break
            elif drop[1] >= k:
                break
        
        return ans

Explain

这个题解的核心思路是使用贪心算法结合两个双端队列（deque）来高效地处理数组。首先，对输入数组nums进行排序，然后使用两个队列q1和q2。q1初始化为排序后的nums，q2用于存放每次操作产生的新元素。在每次操作中，选择q1和q2队头的最小的两个元素进行合并操作，并将结果存入q2。这个过程重复进行，直到所有元素都大于等于k。操作过程中，如果在任意步骤发现已选的任一元素大于等于k，则可以提前结束操作。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        nums.sort()  # 对数组进行排序
        q1 = deque(nums)  # 初始化q1为排序后的nums
        q2 = deque()  # 初始化q2为空
        ans = 0  # 操作次数初始化为0
        
        while q1 or q2:  # 当q1或q2非空时继续操作
            drop = [0] * 2  # 用于存储每次操作选取的两个元素
            for i in range(2):  # 选择两个最小元素
                if not q2 or (q1 and q1[0] <= q2[0]):
                    drop[i] = q1.popleft()  # 从q1取出元素
                else:
                    drop[i] = q2.popleft()  # 从q2取出元素
                if drop[i] >= k:  # 如果任一元素大于等于k，提前结束
                    break
            
            q2.append(drop[0]*2+drop[1])  # 将合成的元素加入q2
            ans += 1  # 操作次数加1
            if drop[0] >= k:  # 如果第一个元素大于等于k
                ans -= 1  # 减去最后一次多加的操作次数
                break
            elif drop[1] >= k:  # 如果第二个元素大于等于k
                break
        
        return ans  # 返回最少操作次数

Explore

使用两个队列可以有效地区分原始数组元素和通过合并操作产生的新元素。q1队列包含排序后的原始数组元素，而q2队列则用来存放每次合并操作后生成的新元素。这种分离使得可以方便地从两个不同来源选择最小元素进行操作。如果只用一个队列，合并生成的新元素和原始元素会混合，使得每次操作时寻找最小的两个元素变得更复杂且效率更低。此外，使用其他数据结构如堆虽然可以维持元素的顺序，但在本问题中，使用两个队列可以更直观且操作简单地实现算法逻辑。

q1队列包含了初始排序后的数组元素，因此q1的元素在初始阶段是整个数据集中最小的。在选择两个最小元素进行合并以逐步增大元素值的过程中，优先选择q1的元素可以保证在早期的操作中使用尽可能小的元素，这有助于控制合成元素的增长速度，并尽可能地延迟较大元素的使用。这种策略有助于在提高每个元素值的同时，尽量减少总的操作次数。

当q1为空而q2包含所有元素时，算法的效率可能会略有下降。这是因为所有的操作必须使用q2中的元素，q2中的元素是之前合成生成的，可能会比q1中原始的最小元素大。尽管如此，由于q2中元素是按照合成顺序逐步增加的，所以这些元素还是相对较小并且合适合并的。在这种情况下，仍然可以进行有效的合并操作，只是整个数组的最小值合成路径变得单一，可能需要更多的合并步骤来达到所有元素都不小于k的目标。