You are given an array of non-negative integers nums
and an integer k
. In one operation, you may choose any element from nums
and increment it by 1
.
【资料图】
Return the maximum product of nums
after at most k
operations. Since the answer may be very large, return it modulo 109 + 7
. Note that you should maximize the product before taking the modulo.
Example 1:
Input: nums = [0,4], k = 5
Output: 20
Explanation: Increment the first number 5 times.Now nums = [5, 4], with a product of 5 * 4 = 20.It can be shown that 20 is maximum product possible, so we return 20.Note that there may be other ways to increment nums to have the maximum product.
Example 2:
Input: nums = [6,3,3,2], k = 2
Output: 216
Explanation: Increment the second number 1 time and increment the fourth number 1 time.Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216.It can be shown that 216 is maximum product possible, so we return 216.Note that there may be other ways to increment nums to have the maximum product.
Constraints:
1 <= nums.length, k <= 105
0 <= nums[i] <= 106
如何让乘积最大,这里面数组里面的数越平均,得到的值就越大,所以我们每次加1的时候,加在最小的那个数上面就可以,所以我们就用优先队列来解决这个问题就可以了
下面是代码:
Runtime: 456 ms, faster than 12.87% of Java online submissions for Maximum Product After K Increments.
Memory Usage: 53.3 MB, less than 58.48% of Java online submissions for Maximum Product After K Increments.
X 关闭
Copyright © 2015-2022 亚洲餐饮网版权所有 备案号:豫ICP备20022870号-9 联系邮箱:553 138 779@qq.com