题目描述：

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]

题目大意：

给定两个长度分别为m与n的数组，数组元素为0-9，每个数组代表一个数字。从这两个数组中选出一些数字，组成一个最大的数，其长度k <= m + n。数组中选出数字的相对顺序应当与原数组保持一致。返回一个包含k个数字的数组。你应当最优化时间和空间复杂度。

测试用例如题目描述。

解题思路：

问题可以转化为这样的两个子问题：

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

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

枚举nums1子数组与nums2子数组的长度len1, len2，在满足长度之和len1+len2等于k的前提下，分别求解最大子数组，并进行合并。

然后从合并得到的子数组中取最大数组即为所求。

子问题1的求解：

参考[LeetCode]Remove Duplicate Letters的思路，利用栈保存最大值子数组

时间复杂度为O(n)，其中n为数组的长度。

子问题2的求解：

两数组的合并可以类比归并排序中的merge操作，只不过在选择两数组中较大的元素时，需要对数组剩余部分的元素进行比较，详见代码。

Python代码：

class Solution(object):
    def maxNumber(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[int]
        """
        def getMax(nums, t):
            ans = []
            size = len(nums)
            for x in range(size):
                while ans and len(ans) + size - x > t and ans[-1] < nums[x]:
                    ans.pop()
                if len(ans) < t:
                    ans += nums[x],
            return ans

        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
        
        len1, len2 = len(nums1), len(nums2)
        res = []
        for x in range(max(0, k - len2), min(k, len1) + 1):
            tmp = merge(getMax(nums1, x), getMax(nums2, k - x))
            res = max(tmp, res)
        return res

merge函数可以简化成一行：

参考：https://leetcode.com/discuss/75804/short-python

def merge(nums1, nums2):
    return [max(nums1, nums2).pop(0) for _ in nums1 + nums2]

 

本文链接：http://bookshadow.com/weblog/2015/12/24/leetcode-create-maximum-number/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码