#leetcode#321.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]

大意：给定两个长为m、n，且均有数字0-9组成的数组，分别代表一个整数，如[1,2,3]代表123，[3,2,1,4]代表3214，一个正整数k,且k<=m+n。从给定的两个数组中选出k个数字组成一个k位数，并使得这个k位数最大。在每一个数组选取数字时，选出的数字在原数组的顺序不能改变。

思路：选出k位数时，第一位需要尽量的大，也就想到从数组nums1选出z个数，从数组nums2选出k-z个数，然后选出开头最大的数字作为第一位。后面的位数可以仿照选区第一位的方式依次选取。合并后即为用选出的k个数组成的最大值。
下面是样例1的部分选取方式：

那么该怎么选出z和k-z个数出来进行合并？
在选出z个数时，我们可以用贪心选择当前数组的z个数能组成的最大值。如：[3,4,6,5],z=1时，选出[6];z=2时，选出[6,5];z=3时,选出[4,6,5]；z=4时，选出[3,4,6,5]等等。首先，计算能够弃掉的数目：drop=len(nums1)-z;遍历nums1，当drop不为0时，维护一个单调非增的栈，当数值小于栈顶，入栈，否则栈顶出栈，继续比较，直到栈空或符合条件。最后取栈的前k个数。同理可以选出另一个数组k-z个数组成的最大值。
下面是数组[3,4,6,5]选取z=2的过程：

最后比较合并后的值，选出最大即可。

代码：

def maxNumber(nums1, nums2, k):
    def findKMax(nums,z):
        drop=len(nums)-z
        stack=[]
        for num in nums:
            while drop and stack and num>stack[-1]:
                stack.pop()
                drop-=1
            stack.append(num)
        return stack[:z]
    x1=abs(min(len(nums1) - k, 0))
    x2=min(len(nums2), k)
    max_arr=[]
    for z in range(x1,x2+1):
        maxNum1=findKMax(nums1, k - z)
        maxNum2=findKMax(nums2, z)
        n=[max(maxNum1, maxNum2).pop(0) for _ in maxNum1+maxNum2]
        max_arr=max(max_arr,n)

    return max_arr