class Solution {
public:
int maximumProduct(vector<int>& nums, int k) {
}
};
2233. K 次增加后的最大乘积
给你一个非负整数数组 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 <= 1050 <= nums[i] <= 106原站题解
cpp 解法, 执行用时: 532 ms, 内存消耗: 88.6 MB, 提交时间: 2023-09-11 16:30:24
class Solution {
const int MOD = 1e9+7;
public:
int maximumProduct(vector<int>& nums, int k) {
priority_queue<int,vector<int>,greater<int>> q;
for(int num : nums){
q.push(num);
}
while(k--){
int num = q.top();q.pop();
q.push(num+1);
}
long res = 1;
while(!q.empty()){
int num = q.top();q.pop();
res=(res*num)%MOD;
}
return (int)res;
}
};
java 解法, 执行用时: 340 ms, 内存消耗: 54.4 MB, 提交时间: 2023-09-11 16:29:56
class Solution {
public int maximumProduct(int[] nums, int k) {
int mod = 1000000007;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : nums) {
pq.offer(num);
}
while (k>0){
k--;
pq.offer(pq.poll()+1);
}
long ans = 1;
while (!pq.isEmpty()){
ans = (ans* pq.poll())% mod;
}
return (int) ans;
}
}
golang 解法, 执行用时: 196 ms, 内存消耗: 8.5 MB, 提交时间: 2023-09-11 16:29:44
func maximumProduct(nums []int, k int) int {
h := hp{nums}
for heap.Init(&h); k > 0; k-- {
h.IntSlice[0]++ // 每次给最小的加一
heap.Fix(&h, 0)
}
ans := 1
for _, num := range nums {
ans = ans * num % (1e9 + 7)
}
return ans
}
type hp struct{ sort.IntSlice }
func (hp) Push(interface{}) {}
func (hp) Pop() (_ interface{}) { return }
python3 解法, 执行用时: 504 ms, 内存消耗: 25.9 MB, 提交时间: 2023-09-11 16:28:36
'''
贪心策略，每次都给最小的数增加1
'''
class Solution:
def maximumProduct(self, nums: List[int], k: int) -> int:
MOD = 10 ** 9 + 7
heapify(nums)
while k:
heapreplace(nums, nums[0] + 1)
k -= 1
ans = 1
for num in nums:
ans = ans * num % MOD
return ans