已知长度分别为 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]

详见：https://leetcode.com/problems/create-maximum-number/description/

C++：

class Solution {public:    vector
     
       maxNumber(vector
      
       & nums1, vector
       
        & nums2, int k)    {        int m = nums1.size();        int n = nums2.size();        vector
        
          result(k);        for (int i = std::max(0 , k - n); i <= k && i <= m; ++i)        {            auto v1 = maxArray(nums1, i);            auto v2 = maxArray(nums2, k - i);            vector
         
           candidate = merge(v1, v2, k);            if (greater(candidate, 0, result, 0))            {                result = candidate;            }        }        return result;    }    bool greater(vector
          
           & nums1, int i, vector
           
            & nums2, int j) { while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) { i++; j++; } return j == nums2.size() || (i
            
              nums2[j]); } vector
             
               merge(vector
              
               & nums1, vector
               
                & nums2, int k) { std::vector
                
                  ans(k); int i = 0, j = 0; for (int r = 0; r
                 

maxArray(vector

& nums, int k) { int n = nums.size(); vector

result(k); for (int i = 0, j = 0; i < n; i++) { while (n - i + j>k && j > 0 && result[j-1] < nums[i]) { j--; } if (j < k) { result[j++] = nums[i]; } } return result; }};