321. 拼接最大数

题目

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

思路

不说了，都在注释里了，喝！

代码

class Solution {
 public:
  vector<int> maxNumber(vector<int> &nums1, vector<int> &nums2, int k) {
    vector<int> result;
    int n1 = nums1.size(), n2 = nums2.size();

    /*初始值含义：如果nums2的大小小于k，那么肯定需要从nums1中取至少k-n2个数，于是i=max(0,k-n2)
      如果nums2的大小大于等于k，那么至少取0个数
      终止值含义：如果k小于n1，那么最多只需要取k个数即可，不需要取n1个数
                 如果k大于等于n1，那么最多就需要取n1个数，但不能取更多了，否则会越界
    */
    for (int i = max(0, k - n2); i <= min(k, n1); i++) {
      //从nums1中取出i个数，从nums2中取出k-i个数
      //先求出两个数组中的最大数
      //再将两个最大数进行合并
      result =
          max(result, maxNumber(maxNumber(nums1, i), maxNumber(nums2, k - i)));
    }
    return result;
  }

 private:
  //子问题1：从一个数组里取出k个数，数的相对顺序需要保证与原数组一致，求这个数的最大值
  vector<int> maxNumber(const vector<int> &nums, int k) {
    //下方代码实际上是用vector模拟了stack
    vector<int> result(k);
    // result目前的大小
    int resultSize = 0;
    for (int i = 0; i < nums.size(); i++) {
      //当result不为空时，nums剩余的值仍足够填满result数组时
      //将nums[i]和result的最后一个值进行比较
      //如果nums[i]>result的最后一个值，那么result应该将最后一个值移除
      while (resultSize > 0 && nums[i] > result[resultSize - 1] &&
             nums.size() - i > k - resultSize) {
        --resultSize;
      }
      //如果目前result大小小于k，则将当前num进行入栈操作
      if (resultSize < k) result[resultSize++] = nums[i];
    }
    return result;
  }

  //子问题2：将两个数组合并成一个最大数，数中的相对顺序需要保持与原数组一致
  vector<int> maxNumber(const vector<int> &nums1, const vector<int> &nums2) {
    vector<int> result(nums1.size() + nums2.size());
    auto s1 = nums1.cbegin(), e1 = nums1.cend(), s2 = nums2.cbegin(),
         e2 = nums2.cend();
    int index = 0;
    while (s1 != e1 || s2 != e2) {
      result[index++] = lexicographical_compare(s1, e1, s2, e2) ? *s2++ : *s1++;
    }
    return result;
  }
};