LeetCode 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 105^550 nums[i] 106^66如果有两个数字a、b且ab如果a加1则其乘积变为(a1)b ab b如果给b加1则乘积变为a(b1) ab a因此给更小的数加1会使乘积更大。我们可以用小顶堆每次给堆顶元素加1即可classSolution{public:intmaximumProduct(vectorintnums,intk){make_heap(nums.begin(),nums.end(),greater());for(inti0;ik;i){pop_heap(nums.begin(),nums.end(),greater());nums.back()1;push_heap(nums.begin(),nums.end(),greater());}intans1;for(inti:nums){ans((longlong)ans*i)%(longlong)(1e97);}returnans;}};如果nums的长度为n则此算法时间复杂度为O(nklogn)空间复杂度为O(1)。