Medium

题目描述

给你一个非负整数数组 nums 和一个整数 k。在一次操作中，你可以选择 nums 中的任意一个元素并将它增加 1。

请你返回在 至多 k 次操作之后，能够得到的 nums 的最大乘积。由于答案可能很大，请你将答案对 10^9 + 7 取余后返回。

注意，你需要将乘积最大化之后再取余。

示例 1：

输入：nums = [0,4], k = 5
输出：20
解释：将第一个数字增加 5 次。
现在 nums = [5, 4]，乘积为 5 * 4 = 20。
可以证明 20 是能够得到的最大乘积，所以我们返回 20。
注意，可能有其他方法将 nums 增加到最大乘积。

示例 2：

输入：nums = [6,3,3,2], k = 2
输出：216
解释：将第二个数字增加 1 次，将第四个数字增加 1 次。
现在 nums = [6, 4, 3, 3]，乘积为 6 * 4 * 3 * 3 = 216。
可以证明 216 是能够得到的最大乘积，所以我们返回 216。
注意，可能有其他方法将 nums 增加到最大乘积。

约束条件：

  • 1 <= nums.length, k <= 10^5
  • 0 <= nums[i] <= 10^6

解题思路

解题思路

要使数组的乘积最大，我们需要采用贪心策略。关键观察是：每次都应该优先增加最小的数字。

为什么要优先增加最小值？

考虑两个数字 a 和 b (其中 a ≤ b)，如果我们只能增加一个数字：

  • 如果增加 a，乘积变化为 (a+1) * b - a * b = b
  • 如果增加 b，乘积变化为 a * (b+1) - a * b = a

由于 a ≤ b，所以增加较小的数字能带来更大的乘积增长。

算法步骤

  1. 使用最小堆存储所有数字
  2. 进行 k 次操作，每次：
    • 取出堆顶（最小值）
    • 将其加 1 后重新放入堆中
  3. 计算最终所有数字的乘积，注意取模

这个贪心策略保证了每一步都能获得最大的乘积增长，从而得到全局最优解。

时间复杂度为 O(k log n)，其中建堆需要 O(n)，k 次堆操作各需要 O(log n)。

代码实现

class Solution {
public:
    int maximumProduct(vector<int>& nums, int k) {
        const int MOD = 1000000007;
        
        // 使用最小堆
        priority_queue<int, vector<int>, greater<int>> minHeap;
        for (int num : nums) {
            minHeap.push(num);
        }
        
        // 进行k次操作
        for (int i = 0; i < k; i++) {
            int smallest = minHeap.top();
            minHeap.pop();
            minHeap.push(smallest + 1);
        }
        
        // 计算乘积
        long long product = 1;
        while (!minHeap.empty()) {
            product = (product * minHeap.top()) % MOD;
            minHeap.pop();
        }
        
        return product;
    }
};

class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        import heapq
        
        MOD = 10**9 + 7
        
        # 建立最小堆
        heapq.heapify(nums)
        
        # 进行k次操作
        for _ in range(k):
            smallest = heapq.heappop(nums)
            heapq.heappush(nums, smallest + 1)
        
        # 计算乘积
        product = 1
        for num in nums:
            product = (product * num) % MOD
        
        return product

public class Solution {
    public int MaximumProduct(int[] nums, int k) {
        const int MOD = 1000000007;
        
        // 使用最小堆
        var minHeap = new PriorityQueue<int, int>();
        foreach (int num in nums) {
            minHeap.Enqueue(num, num);
        }
        
        // 进行k次操作
        for (int i = 0; i < k; i++) {
            int smallest = minHeap.Dequeue();
            minHeap.Enqueue(smallest + 1, smallest + 1);
        }
        
        // 计算乘积
        long product = 1;
        while (minHeap.Count > 0) {
            product = (product * minHeap.Dequeue()) % MOD;
        }
        
        return (int)product;
    }
}

var maximumProduct = function(nums, k) {
    const MOD = 1000000007;
    const minHeap = new MinPriorityQueue();
    
    for (let num of nums) {
        minHeap.enqueue(num);
    }
    
    for (let i = 0; i < k; i++) {
        const min = minHeap.dequeue().element;
        minHeap.enqueue(min + 1);
    }
    
    let product = 1;
    while (!minHeap.isEmpty()) {
        product = (product * minHeap.dequeue().element) % MOD;
    }
    
    return product;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
建堆O(n)O(n)
k次堆操作O(k log n)O(1)
总体O(n + k log n)O(n)

其中 n 是数组长度，k 是操作次数。空间复杂度主要用于存储堆结构。

相关题目