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]

Solution

public class Solution {

    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] max = new int[0];
        for(int i = 0; i <= k; i++) {
            if(nums1.length < i || nums2.length < k - i) continue;
            int[] m = merge(getMax(nums1, i), getMax(nums2, k - i));
            if(bigger(m, 0, max, 0)) max = m;
        }
        return max;
    }

    public int[] getMax(int[] num, int k) {
        int[] ans = new int[k];
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0; i < num.length; i++) {
            while(stack.size() > 0 && num[i] > stack.peek() && (stack.size() - 1) + (num.length - i) >= k) {
                stack.pop();
            }
            if(stack.size() < k) stack.push(num[i]);
        }

        for(int i = k-1; i >= 0; i--) {
            ans[i] = stack.pop();
        }

        return ans;
    }

    public int[] merge(int[] num1, int[] num2) {
        int idx1 = 0;
        int idx2 = 0;
        int ans[] = new int[num1.length + num2.length];
        for(int i = 0; i < num1.length + num2.length; i++) {
            if(bigger(num1, idx1, num2, idx2)) {
                ans[i] = num1[idx1++];
            } else {
                ans[i] = num2[idx2++];
            }
        }
        return ans;
    }

    public boolean bigger(int[] num1, int idx1, int[] num2, int idx2) {
        if(idx1 == num1.length) return false;
        if(idx2 == num2.length) return true;

        int cnt = 0;
        while(idx1 + cnt != num1.length && idx2 + cnt != num2.length) {
            if(num1[idx1 + cnt] > num2[idx2 + cnt]) return true;
            else if(num1[idx1 + cnt] < num2[idx2 + cnt]) return false;
            cnt++;
        }

        return (idx2+cnt) == num2.length;
    }
}