What is the main pattern used in Maximum Product After K Increments?

The main pattern is greedy choice plus invariant validation, incrementing the smallest element repeatedly to maximize the product.

Why is a heap useful for this problem?

A min-heap efficiently tracks the smallest number, ensuring each increment contributes maximally to the product, maintaining the greedy invariant.

How do we handle large products exceeding integer limits?

Apply modulo 10^9+7 during multiplication to prevent overflow while keeping the correct result.

Can we increment multiple elements at once?

Yes, but to maintain the greedy principle, increments should prioritize the current minimal elements first.

What is a common mistake with k increments in this problem?

A frequent error is distributing increments without regard for element size, which can lead to a lower final product.

#2233

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

K 次增加后的最大乘积

给你一个非负整数数组 nums 和一个整数 k 。每次操作，你可以选择 nums 中任一元素并将它增加 1 。请你返回至多 k 次操作后，能得到的 nums 的最大乘积。由于答案可能很大，请你将答案对 10 9 + 7 取余后返回。示例 1：输入： nums = [0,4], k …

数组贪心堆（优先队列）

题目描述

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

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

lightbulb

解题思路

方法一：贪心 + 优先队列（小根堆）

根据题目描述，要使得乘积最大，我们需要尽量增大较小的数，因此我们可以使用小根堆来维护数组 $\textit{nums}$ 。每次从小根堆中取出最小的数，将其增加 $1$ ，然后重新放回小根堆中。重复这个过程 $k$ 次后，我们将当前小根堆中的所有数相乘，即可得到答案。

时间复杂度 $O(k \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        heapify(nums)
        for _ in range(k):
            heapreplace(nums, nums[0] + 1)
        mod = 10**9 + 7
        return reduce(lambda x, y: x * y % mod, nums)

speed

复杂度分析

指标	值
时间	complexity is O(n log n + k log n) due to heap operations for each increment. Space complexity is O(n) for the heap storage.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect a solution that maximizes product using minimal increments first.
question_mark
Using a heap to track the smallest number indicates awareness of greedy invariant.
question_mark
Be ready to discuss modulo arithmetic and why it's applied during multiplication.

warning

常见陷阱

外企场景

error
Incrementing larger numbers first can reduce the final product and violates greedy choice.
error
Not using modulo while multiplying can cause integer overflow.
error
Failing to maintain the heap invariant after each increment results in suboptimal operations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find maximum sum instead of product after k increments using a similar greedy approach.
arrow_right_alt
Allow decrement operations as well and maximize product using mixed greedy decisions.
arrow_right_alt
Compute maximum product if increments must be applied to consecutive elements only.

help

常见问题

外企场景

继续练习

#2208 将数组和减半的最少操作次数 #2333 最小差值平方和 #2335 装满杯子需要的最短总时长