2233. K次增加后的最大乘积

🎯 问题描述（来源于LeetCode）

描述：
给你一个非负整数数组 nums 和一个整数 k。你可以执行以下操作恰好 k 次：
选择 nums 中的任意一个元素，将其值增加 1。
请你返回在执行完 k 次操作后，数组中所有元素的最大乘积。由于答案可能很大，请将结果对 10^9 + 7 取余后返回。

说明：

  • 为了让最终的乘积最大，我们的贪心策略是：每次操作都必须选择当前数组中数值最小的那个元素进行加 1。

  • 只有每次都最大程度地“补齐短板”，才能保证整体乘积的增长幅度最大。

  • 示例：

    • 示例 1：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      输入：nums = [0,4], k = 5
      输出：20
      解释：
      第1次：将0加1，数组变为 [1,4]
      第2次：将1加1，数组变为 [2,4]
      第3次：将2加1，数组变为 [3,4]
      第4次：将3加1，数组变为 [4,4]
      第5次：将4加1，数组变为 [5,4]
      最终乘积为 5 * 4 = 20。
    • 示例 2：
      1
      2
      3
      输入：nums = [6,3,3,2], k = 2
      输出：216
      解释：依次将两个最小的 2 和 3 加 1，最终数组变为 [6,4,4,3]，乘积为 6*4*4*3 = 288（注：具体操作顺序可能不同，但贪心逻辑一致，保证每次选最小值）。

💻 解题思路

思路1：贪心 + 最小堆

代码实现

import heapq
from typing import List

class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        # 将数组转化为最小堆
        heapq.heapify(nums)
        
        # 每次取出堆顶的最小值，加 1 后再放回堆中
        while k:
            val = heapq.heappop(nums)
            heapq.heappush(nums, val + 1)
            k -= 1
        
        # 计算堆中所有元素的乘积
        ans = 1
        mod = 10**9 + 7
        for num in nums:
            ans = (ans * num) % mod
        return ans

📊 性能分析

  • 时间复杂度：O(n+klog⁡n)O(n + k \log n)。建堆需要 O(n)O(n)，每次弹出和推入堆的操作需要 O(log⁡n)O(\log n)，共执行 kk 次。
  • 空间复杂度：O(1)O(1)（如果不计算输入数组的修改）或 O(n)O(n)（取决于堆的实现方式）。

💡 思考

这道题是典型的贪心算法结合**优先队列（堆）**的题目。

  1. 贪心策略：每次给最小的数加 1，能保证每次操作对乘积的提升最大。
  2. 数据结构选择：由于每次操作后，被加 1 的数会变大，需要重新与其他数比较大小以找出新的最小值，使用最小堆可以让我们在 O(1) 的时间内获取最小值，并在 O(log⁡n) 的时间内完成数据的更新。