Make writing a habit together! This is the 14th day of my participation in the “Gold Digging Day New Plan · April More Text Challenge”. Click here for more details

describe

You are given an array of non-negative integers nums and an integer k. In one operation, you may choose any element from nums and increment it by 1.

Return the maximum product of nums after at most k operations. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [0,4], k = 5
Output: 20
Explanation: Increment the first number 5 times.
Now nums = [5, 4], with a product of 5 * 4 = 20.
It can be shown that 20 is maximum product possible, so we return 20.
Note that there may be other ways to increment nums to have the maximum product.
Copy the code

Example 2:

Input: nums = [6,3,3,2], k = 2 Increment the second number 1 time and increment the fourth number 1 time. Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216. It can be shown that 216 is maximum product possible, so we return 216. Note that there may be other ways to increment nums to have the maximum product.Copy the code

Note:

1 <= nums.length, k <= 10^5
0 <= nums[i] <= 10^6
Copy the code

parsing

Given an array of non-negative integers nums and an integer k In a single operation, you can select any element from numS and increment it by one.

Returns the maximum product of all elements in NUMS after a maximum of k such operations. Since the answer is likely to be very large, it returns modulo 10^9 + 7.

Heapq: HeAPQ: HeAPQ: HeAPQ: HeAPQ: HeAPQ: HeAPQ: HeAPQ: HeAPQ

To maximize the final product, the key is to make the smallest number as large as possible, and the idea is simple:

  • Load numS into the heap
  • We do a while loop k times, and each time we pop up the smallest numS number, increment it by one, and then insert it into numS again, minus k by one
  • At the end of the loop, multiply all the elements. Note that every time after the multiplication, you should take the modulus, otherwise the result size will be timed out easily. You can try it yourself
  • I’m going to end up with the largest product, so I’m just going to return it

This problem is just fine for AC because nums is 10^5, and the heap eject time is O(1), which is largely ignored, while the heap insert time is O(logN), and k is at most 10^5. So the total time complexity after k operations is O(NlogN), and the space complexity is O(1).

answer

class Solution(object):
    def maximumProduct(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        heapq.heapify(nums)
        result = 1
        mod = pow(10, 9) + 7
        while k > 0:
            a = heapq.heappop(nums)
            a += 1
            heapq.heappush(nums, a)
            k -= 1
        for n in nums:
            result = (result * n)% mod
        return result
        	      
		
Copy the code

The results

73/73 Test cases passed. Status: Accepted Runtime: 6612 MS Memory Usage: 22.5 MBCopy the code

The original link

Leetcode.com/contest/wee…

Your support is my biggest motivation