321. Create Maximum Number

Problem

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

Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the k digits representing the answer.

  Example 1:

Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]

Example 2:

Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
Output: [6,7,6,0,4]

Example 3:

Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]

  Constraints:

• m == nums1.length

• n == nums2.length

• 1 <= m, n <= 500

• 0 <= nums1[i], nums2[i] <= 9

• 1 <= k <= m + n

Solution

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[]}
 */
var maxNumber = function(nums1, nums2, k) {
     var i, m, n, result = [], subNum1, subNum2, mergedNum;
     for(i = 0; i <= k ; i++){
         if(i > nums1.length || k - i > nums2.length) continue;
         subNum1 = maxSubNum(nums1, i);
         subNum2 = maxSubNum(nums2, k - i);
         mergedNum = [];
         for(m = 0, n = 0; m < subNum1.length && n < subNum2.length;){
             if(compareNums(subNum1, subNum2, m, n) === 1) mergedNum.push(subNum1[m++]);
             else mergedNum.push(subNum2[n++]);
         }
         while(m < subNum1.length) mergedNum.push(subNum1[m++]);
         while(n < subNum2.length) mergedNum.push(subNum2[n++]);
         if(compareNums(mergedNum, result, 0, 0) === 1) result = mergedNum;
     }
     return result;

     function maxSubNum(str, n){
         var i, stack = [], len = str.length;
         for(i = 0; i < len; i++){
             while(stack.length > 0 && stack.length + len - i > n 
                 && stack[stack.length - 1] < str[i]) stack.pop(); 
             if(stack.length < n) stack.push(str[i]);
         }
         return stack;
     }
     /**
      * @return {number} 1 means num1 is larger than num1, the others return -1.
      */
     function compareNums(num1, num2, m, n){
         if(num1[m] === undefined) return -1;
         if(num2[n] === undefined) return 1;
         if(num1[m] > num2[n]) return 1;
         if(num2[n] > num1[m]) return -1;
         return compareNums(num1, num2, m + 1, n + 1); //num1[m] === num2[n]
     }
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).