文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個(gè)非負(fù)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k 。每次操作，你可以選擇 nums 中 任一 元素并將它 增加 1 。

請(qǐng)你返回 至多 k 次操作后，能得到的 nums的 最大乘積 。由于答案可能很大，請(qǐng)你將答案對(duì) 10^9 + 7 取余后返回。

示例 1： 輸入：nums = [0,4], k = 5 輸出：20 解釋：將第一個(gè)數(shù)增加 5 次。 得到 nums = [5, 4] ，乘積為 5 * 4 = 20 。 可以證明 20 是能得到的最大乘積，所以我們返回 20 。 存在其他增加 nums 的方法，也能得到最大乘積。示例 2： 輸入：nums = [6,3,3,2], k = 2 輸出：216 解釋：將第二個(gè)數(shù)增加 1 次，將第四個(gè)數(shù)增加 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 從最小的數(shù)開始增加1，能獲取最大的增長百分比，每次都是對(duì)新的數(shù)組進(jìn)行此操作
• 采用優(yōu)先隊(duì)列，小的優(yōu)先，取出堆頂?shù)?#43;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/

長按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 6039. K 次增加后的最大乘积（优先队列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。