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]

题解

先解决一个问题哈，如果我给你两个数组，把两个数组元素全部选完，再按题目要求拼接乘一个最大数字，怎么拼接呢？比较简单吧，从左到右分别遍历两个数组，大的放前面，比如s1表示第一个数组的下标，s2表示第二个数组下标，那么有。
if nums1[s1]>nums2[s2]:
add(nums1[s1])
elif nums1[s1]<nums2[s2]:
add(nums2[s2])

这个不难理解，但是怎么考虑相等的情况，这个涉及贪心，我们从s1和s2分别一直往后遍历直到nums1[i]!=nums2[j]，
if nums1[i]>nums2[j]:
add(nums1[s1])
elif nums1[i]<nums2[j]:
add(nums2[s2])
这个不难理解吧，那么问题来了，如果一直遍历结束呢，那么这个无所谓了，谁在前都一样，那么如果其中某一个遍历结束，另外一个没有结束呢？
比如i结束但是j没有结束
就需要
if nums2[j]>=nums1[s1]:
add(nums2[s1])
这个不难理解。

这样就处理完毕了，然后就暴力判断，在nums1中选多少个在nums2中选多少个，那么问题来了，如果我在nums1中 选x个，那么肯定要求选取的x个可以构成一个很大的数字，最后把nums1中选取的和nums2中选取的合并起来肯定最大，然后暴力判断这个x是多少，但是我怎么快速的在nums1中选取x个数字可以构成最大呢？

这个又是需要处理。。。。这个题目处理的太多了，先这样分析吧，给一个数组，
[4,7,2,3,1,2,3,4]选取4个，
setp1:在区间[0,4]也就是[4,7,2,3,1]中选最大的为7，下标为1，
setp2:在区间[1+1,5]中也就是[2,3,1,2]中选最大的为3，下标为3，
setp3:在区间[3+1,6]也就是[1,2,3]中选择最大为3,下标为6
Setp4:在[6+1,7]中也就是[4]中选择最大的为4
最后答案7334

希望你理解。

这个可以利用单调栈，找到每个数字在左右区间中最大，那么从左到右遍历，
如果当前的查询区间为[st,et]，并且L[x]<=st and R[x]>=et，那么x肯定为当前区间要找的数字，然后更新st和et为
st=pos[x]+1,et+=1;//pos表示x的下标位置

AC代码

class Solution {
public:
    stack<int>q;
    void Stack_clear()//清空栈函数 
    {
        while(!q.empty())
        q.pop();
    }
    //这里数组以下标1开始
    vector<int> get_L(vector<int>arr)//得到左区间 
    {
        int n=arr.size();
        vector<int>L;
        for(int i=0;i<n;i++)
        L.push_back(i);//初始化
        Stack_clear();
        for(int i=0;i<n;i++)
        {
            if(q.empty()||arr[q.top()]>arr[i])
            q.push(i);
            else
            {
                while(q.empty()==false&&arr[q.top()]<=arr[i])
                {
                    L[i]=L[q.top()];
                    q.pop();
                }
                q.push(i);
            }
        }
        return L;
    }
    vector<int> get_R(vector<int>arr)//得到右区间，其实就是把数组反向遍历的左区间求解 
    {
        int n=arr.size();
        vector<int>R;
        for(int i=0;i<n;i++)
        R.push_back(i);//初始化
        Stack_clear();
        for(int i=n-1;i>=0;i--)
        {
            if(q.empty()||arr[q.top()]>arr[i])
            q.push(i);
            else
            {
                while(q.empty()==false&&arr[q.top()]<=arr[i])
                {
                    R[i]=R[q.top()];
                    q.pop();
                }
                q.push(i);
            }
        }
        return R;
    }
    vector<int>fun(vector<int>nums,vector<int>L,vector<int>R,int k)
    {
        vector<int>res;
        int st=0,et=nums.size()-k;
        for(int i=0;i<nums.size();i++)
        {
            if(L[i]<=st&&R[i]>=et)
            {
                res.push_back(nums[i]);
                st=i+1;
                et=et+1;
            }
        }
        return res;
    }
    vector<int>Contact(vector<int>q1,vector<int>q2)
    {
       // cout<<"here\n";
        vector<int>q;
        int s1=0,s2=0;
        int n1=q1.size()-1,n2=q2.size()-1;
        while(s1<=n1&&s2<=n2)
        {
            //cout<<s1<<" -- "<<s2<<endl;
            if(q1[s1]>q2[s2])
            {
             //   cout<<s1<<" A "<<s2<<endl;
                q.push_back(q1[s1]);
                s1++;
            }
            else if(q1[s1]<q2[s2])
            {
              //  cout<<s1<<" B "<<s2<<endl;
                q.push_back(q2[s2]);
                s2++;
            }
            else
            {
              //  cout<<s1<<" C "<<s2<<endl;
                int i=s1,j=s2;
                while(i<=n1&&j<=n2)
                {
                    if(q1[i]!=q2[j])break;
                    i++;
                    j++;
                }
                if(i>n1&&j>n2)
                {
                    q.push_back(q1[s1]);
                    s1++;
                }
                else if(i<=n1&&j>n2)
                {
                    if(q1[i]>=q2[s2])
                    {
                        q.push_back(q1[s1]);
                        s1++;
                    }
                    else
                    {
                        q.push_back(q2[s2]);
                        s2++;
                    }
                }
                else if(i>n1&&j<=n2)
                {
                    if(q1[s1]<=q2[j])
                    {
                        q.push_back(q2[s2]);
                        s2++;
                    }
                    else
                    {
                        q.push_back(q1[s1]);
                        s1++;
                    }
                }
                else 
                {
                    //cout<<"here"<<q1[s1]<<endl;
                    //cout<<i<<" "<<j<<endl;
                    if(q1[i]>q2[j])
                    {
                        q.push_back(q1[s1]);
                        s1++;
                    }
                    else
                    {
                        q.push_back(q2[s2]);
                        s2++;
                    }
                }
            }
            
        }
        while(s1<=n1)
        {
            q.push_back(q1[s1]);
            s1++;
        }
        while(s2<=n2)
        {
            q.push_back(q2[s2]);
            s2++;
        }
        //cout<<"out\n";
        return q;
    }
    vector<int>Max(vector<int>q1,vector<int>q2)
    {
        for(int i=0;i<q1.size();i++)
        {
            if(q1[i]>q2[i])return q1;
            if(q1[i]<q2[i])return q2;
        }
        return q1;
    }
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) 
    {
       // cout<<nums1.size()<<" "<<nums2.size()<<endl;
        vector<int>L1=get_L(nums1);
        vector<int>R1=get_R(nums1);
        vector<int>L2=get_L(nums2);
        vector<int>R2=get_R(nums2);
        vector<int>res;
        for(int i=0;i<k;i++)
        res.push_back(0);
        for(int x=0;x<=min(k,int(nums1.size()));x++)
        {
            if(k-x>nums2.size())continue;
            res=Max(res,Contact(fun(nums1,L1,R1,x),fun(nums2,L2,R2,k-x)));
        }
        return res;
    }
};