LeetCode 6039. K 次增加后的最大乘积（优先队列）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-after-k-increments
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 从最小的数开始增加1，能获取最大的增长百分比，每次都是对新的数组进行此操作
• 采用优先队列，小的优先，取出堆顶的+1，再放回

class Solution { public:int maximumProduct(vector<int>& nums, int k) {priority_queue<int, vector<int>, greater<int>> q;for(auto num : nums)q.push(num);while(k--){int num = q.top();q.pop();q.push(num+1);}int ans = 1;while(!q.empty()){ans = (1LL*ans*q.top())%1000000007;q.pop();}return ans;} };

440 ms 88.6 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的LeetCode 6039. K 次增加后的最大乘积（优先队列）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。