拼接最大数

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1:

输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]
示例 2:

输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]
示例 3:

输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]

思路：首先我们要先明确限制条件是什么？然后来确定功能安排？

限制条件：原数组中的数字相对位置不得改变，这就意味着我们在选取最大数组的时候不能随意按照数字大小来选取，反而要综合考虑数组中数字大小和其位置（因为我们会有输出数组长度限制）

功能安排： 首先我们先要进行分析，假设如例一所示 nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]，k = 5 我们应该怎么选呢？按照功能描述想要找到组成的最大数组，首先我们应该想到是对于给定每个数组选取个数，我们能否找到其最大组成，然后在对选取个数元组进行遍历，最后进行比较选出最大就可以了。所以功能函数就有了

函数 findmax(sum1,k)：表示对于数组 sum1，找到含有 k 个元素的保持元素相对位置的数组子集
函数 shunxu(sum1,sum2)：表示对给定的两个数组，返回这两个数组可以组成的保持元素相对位置的最大数组
maxNumber(nums1,nums2,k)：完成对所有数组长度选择的遍历，同时完成大小比较

class Solution:
    def findmax(self,sum1,k):#寻找一个数组的最大字串，长度为k
        if k == 0:
            return []
        if len(sum1) == 0:
            return []
        if len(sum1) == k:
                return sum1
        start_range = len(sum1)-k+1
        out = []
        max_num = max(sum1[:start_range])
        max_pos = sum1.index(max_num)
        out.append(max_num)
        next_list = self.findmax(sum1[max_pos+1:],k-1)
        if next_list != None:
            out.extend(next_list)
        return out

    def shunxu(self,sum1,sum2):#对两个数组输出最大组合数组
        if  sum1 == None:
            return sum2
        elif sum2 == None:
            return sum1
        else:
            out = []
            flag = 1
            while flag != 0:
                if sum1 == []:
                    out.extend(sum2)
                    flag = 0                
                    break
                elif sum2 == []:
                    out.extend(sum1)
                    falg = 0                
                    break
                else:
                    if sum1[0] < sum2[0]:
                        out.append(sum2.pop(0))
                        continue
                    elif sum1[0] > sum2[0]:
                        out.append(sum1.pop(0))
                        continue
                    else:
                        i = 0
                        while i < (min(len(sum1),len(sum2))):
                            if sum1[i] > sum2[i]:
                                out.append(sum1.pop(0))
                                break
                            elif sum1[i] < sum2[i]:
                                out.append(sum2.pop(0)) 
                                break
                            else:
                                if i == (min(len(sum1),len(sum2)))-1:
                                    if len(sum1) > len(sum2):
                                        out.append(sum1.pop(0))
                                    elif len(sum1) <= len(sum2):
                                        out.append(sum2.pop(0))
                            i += 1

            return out

    def maxNumber(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[int]
        """
        max_ = [0]*k
        n1 = len(nums1)
        n2 = len(nums2)
        if n1>n2:
            n1,n2,nums1,nums2 = n2,n1,nums2,nums1

        if n1 < k:
            ls = n1
        else:
            ls = k

        if n2 < k:
            start = k - n2
        else:
            start = 0
        if n2 + n1  == k:
            return self.shunxu(nums1,nums2)
        for i in range(start,ls+1):
            ls_n = k-i           
            list_l = self.findmax(nums1,i)
            list_r = self.findmax(nums2,ls_n)            
            out = self.shunxu(list_l,list_r)
            for i in range(k):
                if out[i] > max_[i]:
                    max_ = out
                    break
                elif out[i] < max_[i]:
                    break
        return max_

函数 findmax 的实现很简单：过程是为了保证最后输出数组的长度为 k，且元素保持原来的相对位置，我们使用递归的思想，每一次寻找一个数，这个数字的寻找范围为前 len(sum1)-k 数，找到之后定位最大数，同时在其后以后开始下一次递归寻找子数组的最大数
函数 shunxu 的实现：过程是在两个数组都有元素的情况下通过队列的形式，比较两个数组的第一个数，将较大的那一个数推出，然后循环继续比较。知道最后两个队列有一个为空，将非空队列原样输出即可。
我在这里有一个陷阱：当队列的两个首位数字相等的时候应该选择哪一个输出？我一开始觉得随便输出，一直没能 ac，后来想到还是要比较队列中首位的不同数字，最后将大数所在的那一队列的前面的数字推出。例如 sum1 = [1,2,3,4,5,6,7,7,7,9],sum2 = [1,2,3,4,5,6,7,5] 在这两个队列中，我们发现 0~6 位数字均相等，而 sum1[7] > sum2[7]，所以推出 sum1 的前 7 位，最后合并得到 out1= [1,2,3,4,5,6,7,7,7,9,1,2,3,4,5,6,7,5]，若果随便删，删除 sum2 的话，那么得到的 out2 = [1,2,3,4,5,6,7,5,1,2,3,4,5,6,7,7,7,9], 而按照题意，out1 > out2，所以后面的策略是错误的

• 在思考极端情况的时候，一定要考虑 0，空，满，相等等极端关系情况，做好条件补充的完整性