K 次增加后的最大乘积

标签: 贪心 数组 堆（优先队列）

难度: Medium

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

请你返回 至多 k 次操作后，能得到的 nums的 最大乘积 。由于答案可能很大，请你将答案对 109 + 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 <= 105
  • 0 <= nums[i] <= 106

Submission

运行时间: 159 ms

内存: 25.5 MB

class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        l = 1
        nums.sort()
        nums.append(10**12)
        n = len(nums)
        while k and l < n:
            if nums[l]!= nums[0]:
                dif = nums[l] - nums[0]
                if l * dif <= k:
                    for i in range(l):
                        nums[i] += dif
                    k -= dif * l
                elif l <= k:
                    for i in range(l):
                        nums[i] += k // l
                    k = k % l
                elif l > k:
                    for i in range(k):
                        nums[i] += 1
                    k = 0
            else:
                l += 1
        nums.pop()
        ans = 1
        for x in nums:
            ans = (x *ans) %(10**9+7)
        return ans

Explain

解题思路是首先将数组排序，然后从最小的开始增加，尽可能地让数组中的元素均匀。每次增加操作集中在数组的最小段（即从开始到某一个不再是最小值的元素），这样能最大化乘积。对于每个最小段，如果完全可以将这一段的值增加到下一个不同的值，那么进行增加操作；如果不能，则尽可能均匀地分配增加次数。继续这个操作直到用完所有k次增加机会或者处理完所有元素。最后，计算增加后的数组的乘积，并返回结果。

时间复杂度: O(n^2)

空间复杂度: O(1)

class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        l = 1
        nums.sort()  # 对数组进行排序
        nums.append(10**12)  # 添加一个非常大的数作为哨兵
        n = len(nums)
        while k and l < n:  # 当还有增加次数和未处理完数组时
            if nums[l] != nums[0]:
                dif = nums[l] - nums[0]
                if l * dif <= k:  # 如果能够完全把最小段提升到下一个值
                    for i in range(l):
                        nums[i] += dif
                    k -= dif * l
                elif l <= k:  # 如果剩余增加次数比当前段长度小但可以分配
                    for i in range(l):
                        nums[i] += k // l
                    k = k % l
                elif l > k:  # 如果剩余增加次数比当前段长度还小
                    for i in range(k):
                        nums[i] += 1
                    k = 0
            else:
                l += 1  # 增加l，继续找到下一个不同的值
        nums.pop()  # 移除添加的哨兵
        ans = 1
        for x in nums:  # 计算最终的乘积
            ans = (x * ans) % (10**9 + 7)
        return ans

Explore

在算法中添加一个非常大的数作为哨兵到数组末尾主要是为了处理边界情况。这样做可以避免在增加操作时需要频繁检查是否已经到达数组的末尾。具体来说，这个哨兵元素保证在进行元素值提升的时候，总有一个“下一个不同的值”可以参考，即使实际上已经处理到了原始数组的最后。这样可以简化逻辑并保持循环中的条件判断一致，使代码更加简洁和易于理解。

决定增加操作的策略基于可用的增加次数k与当前段的长度l的比较。如果k足够将当前最小段的所有元素提升至下一个不同的值（即l * dif <= k，其中dif是当前值与下一个不同值的差），则选择将整段提升。如果k不足以完成这一提升但足以均匀分配（即l <= k），则选择均匀分配增加次数。如果k小于段长度l，则选择对前k个元素各增加1，以尽可能平均地利用剩余的次数。这种策略旨在最大化每次增加的效益，以尽可能均匀地提升数组的值，从而最大化最终的乘积。

如果当前段的长度l大于剩余的增加次数k，选择对前k个元素各增加1是为了尽可能地均匀分配有限的增加次数，从而尽可能地使增加后数组的数字均匀。这种方法帮助避免某些数字过高而其他数字仍然较低，从而最大化整个数组的乘积。这种策略是基于贪心算法的思想—即尽可能平均利用每一次增加机会，以达到最佳的整体效果。

在每次乘法操作后立即对结果取模主要是为了防止整数溢出，并保持计算结果的稳定性。因为在多次连续的乘法操作中，尤其是在元素值可能很大或数组很长的情况下，乘积很快会超过常规整数类型的存储范围。取模操作（模一个大质数，如10^9+7）可以有效控制结果在一个安全的数值范围内，同时也是许多编程比赛和实际应用中常用的方法，以确保结果的正确性和程序的健壮性。