前往
大廳
主題

LeetCode - 2233. Maximum Product After K Increments 解題心得

Not In My Back Yard | 2022-12-19 12:00:01 | 巴幣 100 | 人氣 199

題目連結:


題目意譯:
你被給定一非負整數 nums 以及一整數 k。在一次操作中,你可以選擇 nums 中的任一元素並將其值增加 1。

回傳最多 k 次操作之後 nums 所能得到的最大元素乘積值。由於答案可能很大,先將其模 10 ^ 9 + 7 後再回傳。注意到你在進行模運算之前應最大化乘積值。

限制:
1 ≦ nums.length, k ≦ 10 ^ 5
0 ≦ nums[i] ≦ 10 ^ 6



範例測資:
範例 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 中的元素並得到最大乘積值。


解題思維:
可以看到雖然題目是說最多 k 次的操作,但是實際上加了一定比較好,所以這 k 次操作都會做好做滿。

而根據算幾不等式(即算術平均 ≧ 幾何平均,而我們的算術平均不變,都是(nums 中數字總和 + k)除以 nums 元素量),每一項數值越接近彼此(也就是每個數字盡可能地接近算術平均本身),幾何平均值就越大。

因此每次我們可以抓出當前 nums 中的最小值(如果有多個,就隨便取一個元素出來即可;而這個部分可以用一個優先佇列(Priority Queue)實作)將其 + 1。做滿 k 次即可。

最後把 nums 的數字相乘即為所求(記得模 10 ^ 9 + 7)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作