K 증분 후 최대 제품

음수가 아닌 정수nums와 정수k의 배열이 제공됩니다. 한 작업에서 nums에서 요소를 선택하고 1만큼 증가시킬 수 있습니다.

최대 nums개의 작업 후 k의 최대 곱을 반환합니다. 답이 매우 클 수 있으므로 모듈로 109 + 7 로 반환합니다. 모듈로를 사용하기 전에 제품을 최대화해야 합니다.

예 1:

입력: 숫자 = [0,4], k = 5
출력: 20
설명: 첫 번째 숫자를 5번 증가시킵니다.
이제 nums = [5, 4], 곱은 5 * 4 = 20입니다.
20이 가능한 최대 제품임을 알 수 있으므로 20을 반환합니다.
최대 곱을 갖도록 숫자를 증가시키는 다른 방법이 있을 수 있습니다.

예 2:

입력: 숫자 = [6,3,3,2], k = 2
출력: 216
설명: 두 번째 숫자를 1번 증가시키고 네 번째 숫자를 1번 증가시킵니다.
이제 nums = [6, 4, 3, 3]이고 결과는 6 * 4 * 3 * 3 = 216입니다.
216이 가능한 최대 제품임을 알 수 있으므로 216을 반환합니다.
최대 곱을 갖도록 숫자를 증가시키는 다른 방법이 있을 수 있습니다.

제약:

1 <= nums.length, k <= 105

0 <= nums[i] <= 106

해결책:

import heapq

class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        MAX = 10 ** 9 + 7
        n = len(nums)
        heap = []
        deleted = {}
        for i, num in enumerate(nums):
            heapq.heappush(heap, (num, i))
        for _ in range(k):
            curr, j = heapq.heappop(heap)
            while (curr, j) in deleted:
                deleted[(curr, j)] -= 1
                if deleted[(curr, j)] == 0:
                    del deleted[(curr, j)]
                curr, j = heapq.heappop(heap)
            nums[j] += 1
            deleted[(curr, j)] = deleted.get((curr, j), 0) + 1
            heapq.heappush(heap, (curr + 1, j))
        p = 1
        for num in nums:
            p = (p * num) % MAX
        return p