Create Maximum Number
c++solution\ntime and space surpass 90%+\n\n#include<bits/stdc++.h>\nusing namespace std;\n// #define DEBUG\nclass Solution {\npublic:\n  vector<int> maxNumber(
c++solution\ntime and space surpass 90%+\n```\n#include<bits/stdc++.h>\nusing namespace std;\n// #define DEBUG\nclass Solution {\npublic:\n  vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {\n    int m = nums1.size(), n = nums2.size();\n    int *ret = NULL;\n    if(m > n) {\n      return maxNumber(nums2, nums1, k);\n    }\n    // make sure that m is smaller than or equal to m\n    int begin = max(0, k-n);\n    int end = min(m, k);\n    for(int i = begin; i <= end; i++) {\n      int *maxSub1 = maxSubsequence(nums1, i);\n      int *maxSub2 = maxSubsequence(nums2, k - i);\n      #ifdef DEBUG\n      cout << i << "---------------------------\\n";\n      dump(maxSub1, i);\n      dump(maxSub2, k-i);\n      cout << "-------------------------\\n";\n      #endif\n      int *maxSub = merge(maxSub1, i, maxSub2, k-i);\n      ret = comapreAndSwap(ret, maxSub, k);\n    }\n    return vector<int>(ret, ret + k);\n  }\n  void dump(int *sub, int size) {\n    for(int i = 0; i < size; i++) {\n      cout << sub[i] << " ";\n    }\n    cout << endl;\n    return;\n  }\n  int *maxSubsequence(vector<int> &nums, int k) {\n    int n = nums.size();\n    int discard = n-k;\n    int *ret = (int *)malloc(k * sizeof(int));\n    int top = 0;\n    for(auto i : nums) {\n      while(top > 0 && ret[top-1] < i && discard > 0) {\n        discard--;\n        top--;\n      }\n\n      if(top < k) {\n        ret[top++] = i;\n      }else{\n        discard--;\n      }\n    }\n    return ret;\n  }\n\n  int *merge(int *sub1, int size1, int *sub2, int size2) {\n    int idx1 = 0, idx2 = 0;\n    int *ret = (int *)malloc((size1 + size2) * sizeof(int));\n    for(int i = 0; i < size1 + size2; i++) {\n      if(compare(sub1, size1, idx1, sub2, size2, idx2)) {\n        ret[i] = sub1[idx1++];\n      }else{\n        ret[i] = sub2[idx2++];\n      }\n    }\n    free(sub1);\n    free(sub2);\n    return ret;\n  }\n\n  int *comapreAndSwap(int *ret, int *sub, int k) {\n    if(compare(ret, k, 0, sub, k, 0)) {\n      free(sub);\n      return ret;\n    }else{\n      free(ret);\n      return sub;\n    }\n  }\n\n  int compare(int *sub1, int size1, int idx1, int *sub2, int size2, int idx2) {\n    if(size1 == idx1 || sub1 == NULL) {\n      return 0;\n    }else if(size2 == idx2) {\n      return 1;\n    }\n\n    if(sub1[idx1] > sub2[idx2]) {\n      return 1;\n    }else if(sub1[idx1] < sub2[idx2]){\n      return 0;\n    }else{\n      return compare(sub1, size1, idx1+1, sub2, size2, idx2+1);\n    }\n  }\n};\n\n```
[]