LeetCode. 2233. K 次增加后的最大乘积（数学/最小堆）

• 题目
• 方法一：最小堆
• Reference

• 2233. K 次增加后的最大乘积

提示：数组中有两个元素，可以执行一次增加操作，那么选择较小的元素进行增加操作会使得最终乘积最大

证明：用 x , y ( x ≥ y ) x, y (x ge y) x,y(x≥y) 来表示两个元素，对较大元素进行操作后的乘积为 ( x + 1 ) y = x y + y (x + 1)y = xy + y (x+1)y=xy+y，而对较小元素进行操作后的乘积为 x ( y + 1 ) = x y + x x(y + 1) = xy + x x(y+1)=xy+x，两者相减有：
( x + 1 ) y − x ( y + 1 ) = x y + y − ( x y + x ) = y − x < 0 (x+1)y - x(y+1) = xy + y - (xy+x) = y - x < 0 (x+1)y−x(y+1)=xy+y−(xy+x)=y−x<0
因此选择较小的元素进行增加操作会使得最终乘积最大。

推广：上述结论可以很容易地推广到 n n n 个元素，为了使得最终数组元素乘积最大，需要在每次操作时都选择数值最小的元素进行增加操作。

对于每一次加一操作，对所有数字中最小的那个加一，得到的新增贡献最大，进行 k k k次操作后的最大乘积值就是每次操作最优的后果，即 局部最优 可得到 全局最优

算法流程：

• 把数组nums中的所有元素放入最小堆中
• 循环k次，每次取出堆顶元素（最小值），并对其进行加一操作，再放回堆中
• 把堆中的所有元素相乘并取余

class Solution {
    public int maximumProduct(int[] nums, int k) {
        // 默认小根堆
        PriorityQueue pq = new PriorityQueue<>();
        for (int num : nums) {
            pq.offer(num);
        }
        for (int i = 0; i < k; i++) {
            // 弹出堆顶最小值+1
            int num = pq.poll() + 1;
            // 重新放入堆中
            pq.offer(num);
        }
        long ans = 1, mod = 1000000007;
        while (!pq.isEmpty()) {
            ans = (ans * pq.poll()) % mod;
        }
        return (int) ans;
    }
}

• 时间复杂度： O ( n + k log ⁡ n ) O(n + klog n) O(n+klogn)，其中 n n n 为 nums textit{nums} nums 的长度。建堆的复杂度为 O ( n ) O(n) O(n)；每次弹出最小值与添加新值的时间复杂度为 O ( log ⁡ n ) O(log n) O(logn)，共需进行 k k k 次

• 空间复杂度： O ( n ) O(n) O(n)

• K 次增加后的最大乘积

• 贪心+优先队列