solution.md

# 拼接最大数

<p>给定长度分别为&nbsp;<code>m</code>&nbsp;和&nbsp;<code>n</code>&nbsp;的两个数组，其元素由&nbsp;<code>0-9</code>&nbsp;构成，表示两个自然数各位上的数字。现在从这两个数组中选出 <code>k (k &lt;= m + n)</code>&nbsp;个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。</p>

<p>求满足该条件的最大数。结果返回一个表示该最大数的长度为&nbsp;<code>k</code>&nbsp;的数组。</p>

<p><strong>说明: </strong>请尽可能地优化你算法的时间和空间复杂度。</p>

<p><strong>示例&nbsp;1:</strong></p>

<pre><strong>输入:</strong>
nums1 = <code>[3, 4, 6, 5]</code>
nums2 = <code>[9, 1, 2, 5, 8, 3]</code>
k = <code>5</code>
<strong>输出:</strong>
<code>[9, 8, 6, 5, 3]</code></pre>

<p><strong>示例 2:</strong></p>

<pre><strong>输入:</strong>
nums1 = <code>[6, 7]</code>
nums2 = <code>[6, 0, 4]</code>
k = <code>5</code>
<strong>输出:</strong>
<code>[6, 7, 6, 0, 4]</code></pre>

<p><strong>示例 3:</strong></p>

<pre><strong>输入:</strong>
nums1 = <code>[3, 9]</code>
nums2 = <code>[8, 9]</code>
k = <code>3</code>
<strong>输出:</strong>
<code>[9, 8, 9]</code></pre>

<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    vector<int> nums1 = {3, 4, 6, 5};
    vector<int> nums2 = {9, 1, 2, 5, 8, 3};
    int k = 5;
    vector<int> 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<int> maxNumber(vector<int> &nums1, vector<int> &nums2, int k)
    {
        int n = nums1.size();
        int m = nums2.size();
        struct node all[m + n];
        vector<int> 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<int> getNumsFromVector(vector<int> &nums, int k)
    {
        int n = nums.size();
        if (n == 0)
            return {};
        vector<int> 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<int> res(stack.begin(), stack.begin() + k);
            return res;
        }
        return stack;
    }

    int maxNumsVector(vector<int> &nums1, int index1, vector<int> &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<int> merge(vector<int> &nums1, vector<int> &nums2)
    {
        int m = nums1.size(), n = nums2.size();
        if (m == 0)
            return nums2;
        if (n == 0)
            return nums1;
        vector<int> 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<int> maxNumber(vector<int> &nums1, vector<int> &nums2, int k)
    {
        int m = nums1.size();
        int n = nums2.size();

        int begin = max(0, k - n), end = min(k, m);
        vector<int> ansNums(k, 0);
        for (int i = begin; i <= end; ++i)
        {
            vector<int> tempNums1 = getNumsFromVector(nums1, i);
            vector<int> tempNums2 = getNumsFromVector(nums2, k - i);
            vector<int> mergeRes = merge(tempNums1, tempNums2);
            if (maxNumsVector(ansNums, 0, mergeRes, 0) == 2)
            {
                ansNums = mergeRes;
            }
        }
        return ansNums;
    }
};
```

### B
```cpp
class Solution
{
public:
    vector<int> find_kMax(vector<int> &num, int k)
    {
        vector<int> 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<int> merge(vector<int> &nums1, vector<int> &nums2)
    {
        vector<int> 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<int> maxNumber(vector<int> &nums1, vector<int> &nums2, int k)
    {
        vector<int> 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<int> maxNumber(vector<int> &nums1, vector<int> &nums2, int k)
    {
        int m = nums1.size(), n = nums2.size();
        vector<int> 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<int> maxVector(vector<int> nums, int k)
    {
        int drop = nums.size() - k;
        vector<int> 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<int> mergeVector(vector<int> nums1, vector<int> nums2)
    {
        vector<int> res;
        while (nums1.size() + nums2.size())
        {
            vector<int> &tmp = nums1 > nums2 ? nums1 : nums2;
            res.push_back(tmp[0]);
            tmp.erase(tmp.begin());
        }
        return res;
    }
};
```