本文共 2193 字，大约阅读时间需要 7 分钟。

给定长度分别为 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]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/create-maximum-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

，说的非常详细 假设最大子序列中，包含来自nums1的s个元素和来自nums2的k-s个元素，那么可以通过反证法证明，来自nums1的s个元素，构成了nums1的长度为s的最大子序列；来自nums2的k-s个元素，构成了nums2的长度为k-s的最大子序列。因此，可以首先分别求出nums1中长度为s的最大子序列，和nums2中长度为k-s的最大子序列，然后求它们归并起来的最大子序列的长度，最后对一切可能的s求最大值。代码如下：

class Solution {
   public:    vector
   
     maxNumber(vector
    
     & nums1, vector
     
      & nums2, int k) {
           vector
      
        res(k, 0);        int n = nums1.size(), m = nums2.size();        // 假设有最大子序列中有s个元素来自nums1，对所有可能的s值遍历        for (int s=max(0, k-m); s<=min(k, n); s++){
               vector
       
         temp;            int i = 0, j = 0;            // nums1中长度为s的最大子序列            vector
        
          temp1 = maxKsequence(nums1, s); // nums2中长度为k-s的最大子序列 vector
         
           temp2 = maxKsequence(nums2, k-s); // 对两个子序列进行归并 // lexicographical_compare：比较两个序列的字典序大小 auto iter1 = temp1.begin(), iter2 = temp2.begin(); while (iter1 != temp1.end() || iter2 != temp2.end()){ temp.push_back(lexicographical_compare(iter1, temp1.end(), iter2, temp2.end()) ? *iter2++ : *iter1++); } // 如果归并后的最大子序列大于目前已找到的最大子序列，则更新解 res = lexicographical_compare(res.begin(), res.end(), temp.begin(), temp.end()) ? temp : res; } return res; } // 求数组v的长度为k的最大子序列 vector
          
            maxKsequence(vector
           
             v, int k){ int n = v.size(); if (n <= k) return v; vector
            
              res; int pop = n-k; for (int i=0; i
             
              res.back() && pop-->0) res.pop_back(); res.push_back(v[i]); } res.resize(k); return res; }};/*作者：Gorilla链接：https://leetcode-cn.com/problems/create-maximum-number/solution/cshou-xian-qiu-jie-zi-wen-ti-zai-he-bing-zi-wen-ti/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/