卖萌的弱渣

I am stupid, I am hungry.

Create Maximum Number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9] nums2 = [8, 9] k = 3 return [9, 8, 9]

Solution

  1. 从数组nums中挑选出t个数，在保持元素相对顺序不变的情况下，使得选出的子数组最大化。

  2. 在保持元素相对顺序不变的前提下，将数组nums1与数组nums2合并，使合并后的数组最大化。

(Create-Maximum-Number.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution(object):
    def maxNumber(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[int]
        """

        # 在数组中找到长度为k的最大子数组
        def find_max_sub_array(nums, k):
            # 维护当前最大子数组
            stack = []
            n = len(nums)
            for i in range(n):
                # 若stack已满，而且nums[i]比stack最后一个要大,则把stack[-1]弹出，插入nums[i]
                while stack and len(stack) + n - i > k and nums[i] > stack[-1]:
                    stack.pop()
                if len(stack) < k:
                    stack.append(nums[i])
            return stack


        l1 = len(nums1)
        l2 = len(nums2)

        ret = [0]*k
        for i in range(max(0,k-l2), min(k,l1)+1):
            sub1 = find_max_sub_array(nums1, i)
            sub2 = find_max_sub_array(nums2, k-i)
            ret = max(ret, [max(sub1,sub2).pop(0) for x in range(k)])
        return ret