题目

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

方法一：最小堆

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

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

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

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

算法流程：

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

class Solution {
    public int maximumProduct(int[] nums, int k) {
        // 默认小根堆
        PriorityQueue<Integer> 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)$，其中 $n$ 为 $\text{nums}$ 的长度。建堆的复杂度为 $O(n)$；每次弹出最小值与添加新值的时间复杂度为 $O(\log n)$，共需进行 $k$ 次

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

Reference

• K 次增加后的最大乘积

• 贪心+优先队列