# 拼接最大数
给定长度分别为 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]
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
int main()
{
Solution sol;
vector nums1 = {3, 4, 6, 5};
vector nums2 = {9, 1, 2, 5, 8, 3};
int k = 5;
vector res = sol.maxNumber(nums1, nums2, k);
for (auto i : res)
cout << i << " ";
return 0;
}
```
## 答案
```cpp
class Solution
{
public:
struct node
{
int val;
int vec;
int pos;
};
static bool cmp(node a, node b)
{
return a.val > b.val;
}
vector maxNumber(vector &nums1, vector &nums2, int k)
{
int n = nums1.size();
int m = nums2.size();
struct node all[m + n];
vector ans;
for (int i = 0; i < n; i++)
{
all[i].vec = 1;
all[i].val = nums1[i];
all[i].pos = i;
}
for (int i = 0; i < m; i++)
{
all[i + n].vec = 2;
all[i + n].val = nums2[i];
all[i + n].pos = i;
}
sort(all, all + m + n, cmp);
int now1 = 0;
int now2 = 0;
int st = 0;
while (st != n + 1)
{
for (int i = 0; i < n + m; i++)
{
if (all[i].pos >= now1 && n - all[i].pos + m - now2 >= k - st)
{
ans.push_back(all[i].val);
now1 = all[i].pos + 1;
st++;
break;
}
}
}
return ans;
}
};
```
## 选项
### A
```cpp
class Solution
{
public:
vector getNumsFromVector(vector &nums, int k)
{
int n = nums.size();
if (n == 0)
return {};
vector stack;
stack.push_back(nums[0]);
for (int i = 1; i < n; ++i)
{
while (!stack.empty() && nums[i] > stack.back() && (n - i > k - (int)stack.size()))
{
stack.pop_back();
}
stack.push_back(nums[i]);
}
if (stack.size() > k)
{
vector res(stack.begin(), stack.begin() + k);
return res;
}
return stack;
}
int maxNumsVector(vector &nums1, int index1, vector &nums2, int index2)
{
int m = nums1.size(), n = nums2.size();
if (m == 0)
return 2;
if (n == 0)
return 1;
int p1 = index1, p2 = index2;
for (; p1 < m && p2 < n; ++p1, ++p2)
{
if (nums1[p1] < nums2[p2])
{
return 2;
}
if (nums1[p1] > nums2[p2])
{
return 1;
}
}
if (p1 < m)
{
return 1;
}
else
{
return 2;
}
}
vector merge(vector &nums1, vector &nums2)
{
int m = nums1.size(), n = nums2.size();
if (m == 0)
return nums2;
if (n == 0)
return nums1;
vector res(m + n, 0);
int p1 = 0, p2 = 0;
int i = 0;
while (p1 < m && p2 < n)
{
if (nums1[p1] < nums2[p2])
{
res[i++] = nums2[p2++];
}
else if (nums1[p1] == nums2[p2])
{
if (maxNumsVector(nums1, p1, nums2, p2) == 1)
{
res[i++] = nums1[p1++];
}
else
{
res[i++] = nums2[p2++];
}
}
else
{
res[i++] = nums1[p1++];
}
}
while (p1 < m)
{
res[i++] = nums1[p1++];
}
while (p2 < n)
{
res[i++] = nums2[p2++];
}
return res;
}
vector maxNumber(vector &nums1, vector &nums2, int k)
{
int m = nums1.size();
int n = nums2.size();
int begin = max(0, k - n), end = min(k, m);
vector ansNums(k, 0);
for (int i = begin; i <= end; ++i)
{
vector tempNums1 = getNumsFromVector(nums1, i);
vector tempNums2 = getNumsFromVector(nums2, k - i);
vector mergeRes = merge(tempNums1, tempNums2);
if (maxNumsVector(ansNums, 0, mergeRes, 0) == 2)
{
ansNums = mergeRes;
}
}
return ansNums;
}
};
```
### B
```cpp
class Solution
{
public:
vector find_kMax(vector &num, int k)
{
vector res;
int i = 0;
while (k > 0)
{
int idx = i;
for (; i < num.size() - k + 1; ++i)
{
if (num[i] > num[idx])
idx = i;
}
res.push_back(num[idx]);
i = idx + 1;
--k;
}
return res;
}
vector merge(vector &nums1, vector &nums2)
{
vector res;
for (auto iter1 = nums1.begin(), iter2 = nums2.begin(); iter1 != nums1.end() || iter2 != nums2.end();)
{
if (lexicographical_compare(iter1, nums1.end(), iter2, nums2.end()))
res.push_back(*iter2++);
else
res.push_back(*iter1++);
}
return res;
}
vector maxNumber(vector &nums1, vector &nums2, int k)
{
vector res;
for (int i = 0; i <= k; ++i)
{
int j = k - i;
if (i > nums1.size() || j > nums2.size())
continue;
auto tmp1 = find_kMax(nums1, i);
auto tmp2 = find_kMax(nums2, j);
res = max(res, merge(tmp1, tmp2));
}
return res;
}
};
```
### C
```cpp
class Solution
{
public:
vector maxNumber(vector &nums1, vector &nums2, int k)
{
int m = nums1.size(), n = nums2.size();
vector res;
for (int i = max(0, k - n); i <= min(k, m); i++)
res = max(res, mergeVector(maxVector(nums1, i), maxVector(nums2, k - i)));
return res;
}
vector maxVector(vector nums, int k)
{
int drop = nums.size() - k;
vector res;
for (int num : nums)
{
while (drop && res.size() && res.back() < num)
{
res.pop_back();
--drop;
}
res.push_back(num);
}
res.resize(k);
return res;
}
vector mergeVector(vector nums1, vector nums2)
{
vector res;
while (nums1.size() + nums2.size())
{
vector &tmp = nums1 > nums2 ? nums1 : nums2;
res.push_back(tmp[0]);
tmp.erase(tmp.begin());
}
return res;
}
};
```