動機

沒有魔法的一題

但要怎麼看出沒有魔法?

Problem

You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.

Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the k digits representing the answer.

 

Example 1:

Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5Output: [9,8,6,5,3]

Example 2:

Input: nums1 = [6,7], nums2 = [6,0,4], k = 5Output: [6,7,6,0,4]

Example 3:

Input: nums1 = [3,9], nums2 = [8,9], k = 3Output: [9,8,9]

 

Constraints:

  • m == nums1.length
  • n == nums2.length
  • 1 <= m, n <= 500
  • 0 <= nums1[i], nums2[i] <= 9
  • 1 <= k <= m + n

Sol

如果只是要字典序最大，用monotonic stack就好

接著就是merge，要看字典序大小去merge

最後就是try所有組合

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        def maxList(ns, drop):
            ret = []
            for n in ns:
                while drop > 0 and ret and ret[-1] < n:
                    ret.pop()
                    drop -= 1
                ret.append(n)
            return ret
        def merge(nums1, nums2):
            ans = []
            while nums1 or nums2:
                if nums1 > nums2:
                    ans += [nums1[0]]
                    nums1 = nums1[1:]
                else:
                    ans += [nums2[0]]
                    nums2 = nums2[1:]
            return ans
        ret = []
        for i in range(k):
            a,b = len(nums1)-i, len(nums2)-(k-i)
            if a >= 0 and b >= 0:
                ret = max(ret, merge(maxList(nums1,a),maxList(nums2,b))[:k])
        return ret