Given two arrays of length `m`

and `n`

with digits `0-9`

representing two numbers. Create the maximum number of length `k <= m + n`

from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the `k`

digits. You should try to optimize your time and space complexity.

**Example 1:**

nums1 = `[3, 4, 6, 5]`

nums2 = `[9, 1, 2, 5, 8, 3]`

k = `5`

return `[9, 8, 6, 5, 3]`

**Example 2:**

nums1 = `[6, 7]`

nums2 = `[6, 0, 4]`

k = `5`

return `[6, 7, 6, 0, 4]`

**Example 3:**

nums1 = `[3, 9]`

nums2 = `[8, 9]`

k = `3`

return `[9, 8, 9]`

In order to solve this problem, we should firstly build **int[] maxNumber(int[] num, int k) **function, which returns maximum int array from num[] with length k.

For example:

num[] = {9, 2, 5, 3, 8}, k = 5, return {9, 2, 5, 3, 8}

num[] = {9, 2, 5, 3, 8}, k = 4, return {9, 5, 3, 8}

num[] = {9, 2, 5, 3, 8}, k = 3, return {9, 5, 8}

num[] = {9, 2, 5, 3, 8}, k = 2, return {9, 8}

In order to achieve this function, we use a stack. Basic idea is that it pops stack top if next element is greater than stack top, and number of rest element is enough to fill k elements in stack.

We still need to create a compare function. **int compare(int[] num1, int i, int[] num2, int j)**

It returns positive if num1{i, i+1,…} is “greater” than num2{j, j+1, …}.

It returns negative if num1{i, i+1,…} is “less” than num2{j, j+1, …}.

It returns negative if num1{i, i+1,…} is “equal” to num2{j, j+1, …}.

For example,

num1 = {9, 2, 5, 8, 3}, i = 1, int[] num2= {5, 6, 6}, j = 0. Then we know 2583 is less than 566. So return negative number.

num1 = {9, 2, 5, 8, 3}, i = 2, int[] num2= {5, 6, 6}, j = 0. Then we know 583 is greater than 566. So return positive number.

Then the final solution is that we use this maxNumber function build i elements array from nums1 and k – i elements from nums2(i belongs to [0,…,k]). Then we merge them. When we merge, we should use compare to decide where the next element from.

check my code on github: link