321.md

321 Create Maximum Number

Description

link

---

Solution

设定i为num1从左边开始，j为num2从右边开始的i + j=k，选择对应范围内最大的i/j个数字将其组合起来，最后得到一个最大答案即可

---

Code

Complexity T : O((n+m)^2)

class Solution:
    def maxNumber(self, nums1: 'List[int]', nums2: 'List[int]', k: 'int') -> 'List[int]':
        n, m = len(nums1), len(nums2)
        ans = [0] * k
        for i in range(0, k+1):
            j = k - i
            if i > n or j > m: 
                continue
                
            left = self.maxOneNumber(nums1, n, i)
            right = self.maxOneNumber(nums2, m, j)
            cur = self.merge(collections.deque(left), collections.deque(right))
            ans = max(ans, cur)

        return ans
    
    def maxOneNumber(self, nums, n, k):
        ans = [-1] * k
        j = 0
        for i in range(n):
            while n - i > k - j and j > 0 and ans[j-1] < nums[i]:
                j -= 1
            if j < k:
                ans[j] = nums[i]
                j += 1
        return ans
    
    def merge(self, nums1, nums2):
        ans = []
        while nums1 or nums2:
            if nums1 > nums2:
                ans.append(nums1.popleft())
            else:
                ans.append(nums2.popleft())
        return ans