Medium

题目描述

给你一个下标从 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]。
此时，nums 的所有元素都大于等于 10，所以我们可以停止操作。
可以证明，2 是使所有元素都大于等于 10 所需的最小操作次数。

示例 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，所以我们可以停止操作。
可以证明，4 是使所有元素都大于等于 20 所需的最小操作次数。

提示：

  • 2 <= nums.length <= 2 * 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9
  • 输入保证答案总是存在。也就是说，在执行若干次操作后，数组的所有元素都大于等于 k。

解题思路

这是一个贪心算法问题，需要使用优先队列（最小堆）来高效地找到数组中的最小元素。

核心思路： 每次操作都选择数组中最小的两个元素进行合并，这样可以最大程度地减少操作次数。因为每次合并都会产生一个更大的数值，而我们的目标是让所有元素都达到阈值 k。

算法步骤：

  1. 将所有元素放入最小堆中
  2. 当堆中存在小于 k 的元素时，重复以下操作：
    • 取出最小的两个元素 x 和 y
    • 计算新值：min(x, y) * 2 + max(x, y)
    • 将新值重新放入堆中
    • 操作次数加1
  3. 返回总操作次数

为什么选择最小的两个元素？

  • 合并较小的元素能更快地将它们"升级"到阈值以上
  • 保留较大的元素可以在后续操作中作为合并的基础
  • 这种贪心策略能保证最少的操作次数

时间复杂度主要来自堆操作，每次操作需要 O(log n) 的时间复杂度。

推荐解法： 使用优先队列的贪心算法

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        priority_queue<long long, vector<long long>, greater<long long>> pq;
        
        for (int num : nums) {
            pq.push(num);
        }
        
        int operations = 0;
        while (pq.size() > 1 && pq.top() < k) {
            long long x = pq.top(); pq.pop();
            long long y = pq.top(); pq.pop();
            
            long long newVal = min(x, y) * 2 + max(x, y);
            pq.push(newVal);
            operations++;
        }
        
        return operations;
    }
};

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        import heapq
        
        heap = nums[:]
        heapq.heapify(heap)
        
        operations = 0
        while len(heap) > 1 and heap[0] < k:
            x = heapq.heappop(heap)
            y = heapq.heappop(heap)
            
            new_val = min(x, y) * 2 + max(x, y)
            heapq.heappush(heap, new_val)
            operations += 1
        
        return operations

public class Solution {
    public int MinOperations(int[] nums, int k) {
        var pq = new PriorityQueue<long, long>();
        
        foreach (int num in nums) {
            pq.Enqueue(num, num);
        }
        
        int operations = 0;
        while (pq.Count > 1 && pq.Peek() < k) {
            long x = pq.Dequeue();
            long y = pq.Dequeue();
            
            long newVal = Math.Min(x, y) * 2 + Math.Max(x, y);
            pq.Enqueue(newVal, newVal);
            operations++;
        }
        
        return operations;
    }
}

var minOperations = function(nums, k) {
    const minHeap = new MinPriorityQueue();
    
    for (const num of nums) {
        minHeap.enqueue(num);
    }
    
    let operations = 0;
    
    while (minHeap.size() > 1 && minHeap.front().element < k) {
        const x = minHeap.dequeue().element;
        const y = minHeap.dequeue().element;
        const newVal = Math.min(x, y) * 2 + Math.max(x, y);
        minHeap.enqueue(newVal);
        operations++;
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)其中 n 是数组长度，需要进行最多 n-1 次操作，每次操作涉及堆的插入和删除操作，复杂度为 O(log n)
空间复杂度O(n)优先队列存储所有元素所需的空间

相关题目