<p>You are given two integer arrays <code>nums1</code> and <code>nums2</code> of lengths <code>m</code> and <code>n</code> respectively. <code>nums1</code> and <code>nums2</code> represent the digits of two numbers. You are also given an integer <code>k</code>.</p>

<p>Create the maximum number of length <code>k &lt;= m + n</code> from digits of the two numbers. The relative order of the digits from the same array must be preserved.</p>

<p>Return an array of the <code>k</code> digits representing the answer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
<strong>Output:</strong> [9,8,6,5,3]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [6,7], nums2 = [6,0,4], k = 5
<strong>Output:</strong> [6,7,6,0,4]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [3,9], nums2 = [8,9], k = 3
<strong>Output:</strong> [9,8,9]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == nums1.length</code></li>
	<li><code>n == nums2.length</code></li>
	<li><code>1 &lt;= m, n &lt;= 500</code></li>
	<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 9</code></li>
	<li><code>1 &lt;= k &lt;= m + n</code></li>
</ul>

class Solution {
public:
    vector<int> removeKdigits(vector<int> num, int k) {
        // cout<<num.size()<<" : "<<k<<endl;
        stack<int>st;
        for(auto &it:num){
           while(!st.empty() && st.top() < it && k){
               k--;
               st.pop();
            }
            st.push(it); 
        }
        while(!st.empty() && k){
            st.pop();
            k--;
        }
        // cout<<k<<endl;;
        vector<int>ans;
        while(!st.empty()){
            ans.push_back(st.top());
            st.pop();
            k--;
        }
        // while(ans.size() > 1 && ans.back()==0)ans.pop_back();
        reverse(ans.begin(),ans.end());
        return ans;
     }
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        if(nums1.size()>nums2.size())swap(nums1,nums2);
        int n = nums1.size();
        int m = nums2.size();
        vector<int>ans;
        for(int i = 0 ; i <= min(k,n);i++){
            if(k-i>m)continue;
            vector<int>v1 = removeKdigits(nums1,n-i);
            // for(auto &it:v1){cout<<it<<" - ";}cout<<endl;
            vector<int>v2 = removeKdigits(nums2,m-(k-i));
            // for(auto &it:v2){cout<<it<<" : ";}cout<<endl;

            vector<int>merge = mergeArrays(v1,v2);
            // for(auto &it:merge){cout<<it<<" * ";}cout<<endl;

            ans = max(ans,merge);
        }
        return ans;
    }
    vector<int> mergeArrays(vector<int>arr1, vector<int>arr2){
            int n1 = arr1.size();
            int n2 = arr2.size();
            // cout<<n1<<" -size- "<<n2<<endl;
            vector<int>arr3(n1+n2);
            int i = 0, j = 0, k = 0;
              while (i< n1 && j < n2){
                if (arr1[i] > arr2[j])
                    arr3[k++] = arr1[i++];
                else if(arr1[i] < arr2[j])
                    arr3[k++] = arr2[j++];
                else {
                    vector<int> tmp1(arr1.begin() + i, arr1.end());
                    vector<int> tmp2(arr2.begin() + j, arr2.end());
                    if(tmp2>tmp1){
                      arr3[k++] = arr2[j++];
                    }else {
                      arr3[k++] = arr1[i++];
                    }
                }
              }
              while (i < n1)
                 arr3[k++] = arr1[i++];

              while (j < n2)
                 arr3[k++] = arr2[j++];
            return arr3;
        }
};

// 2,3
// k = 5
// n = 4 , m = 6
131797