<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:
    bool isNums1GreaterThanNums2(vector<int> &nums1, int idx1, int nums1Size, vector<int> &nums2, int idx2, int nums2Size) {
        while (idx1 < nums1Size && idx2 < nums2Size && nums1[idx1] == nums2[idx2]) {
            idx1++;
            idx2++;
        }

        return (idx2 == nums2Size || (idx1 < nums1Size && nums1[idx1] > nums2[idx2]));
    }

    void mergeSubNums(vector<int> &subNums1, vector<int> &subNums2, int subNumsSize1, int subNumsSize2, vector<int> &candidate, int k) {
        int candIdx = 0;

        for (int idx1 = 0, idx2 = 0; candIdx < k; ++candIdx) {
            if (isNums1GreaterThanNums2(subNums1, idx1, subNumsSize1, subNums2, idx2, subNumsSize2)) {
                candidate[candIdx] = subNums1[idx1++];
            } else {
                candidate[candIdx] = subNums2[idx2++];
            }
        }
    }

    void getMaxSubNums(vector<int> &nums, int targetSize, vector<int> &subNums) {
        int numsSize = nums.size();
        int subNumsSize = 0;

        if (targetSize == 0)
            return;

        for (int numsIdx = 0; numsIdx < numsSize; ++numsIdx) {
            while ((numsSize - numsIdx > targetSize - subNumsSize) && subNumsSize > 0 && subNums[subNumsSize - 1] < nums[numsIdx]) {
                subNumsSize--;
            }

            if (subNumsSize < targetSize) {
                subNums[subNumsSize] = nums[numsIdx];
                subNumsSize++;
            }
        }
    }

    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int numsSize1 = nums1.size();
        int numsSize2 = nums2.size();
        vector<int> answer, candidate(k);
        vector<int> subNums1(numsSize1), subNums2(numsSize2);

        for (int subNumsSize1 = max(0, k - numsSize2); subNumsSize1 <= k && subNumsSize1 <= numsSize1; ++subNumsSize1) {
            getMaxSubNums(nums1, subNumsSize1, subNums1);
            getMaxSubNums(nums2, k - subNumsSize1, subNums2);

            mergeSubNums(subNums1, subNums2, subNumsSize1, k - subNumsSize1, candidate, k);

            if (isNums1GreaterThanNums2(candidate, 0, candidate.size(), answer, 0, answer.size())) {
                answer = candidate;
            }
        }

        return answer;
    }
};
17007