[LeetCode][JavaScript]Create Maximumber

クリアーMaximumber
Gven two arrays of length  m and  n with digits  0-9 representing two numbers.Create the maximnumber 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 shoud try to optimize your time and space coplexity.
Example 1:
nums 1=  [3, 4, 6, 5] nums 2=  [9, 1, 2, 5, 8, 3] k=  5リセット  [9, 8, 6, 5, 3]Example 2:
nums 1=  [6, 7] nums 2=  [6, 0, 4] k=  5リセット  [6, 7, 6, 0, 4]Example 3:
nums 1=  [3, 9] nums 2=  [8, 9] k=  3リセット  [9, 8, 9]https://leetcode.com/problems/create-maximum-number/
 
 
 
 
長い間見ましたが、最後に一つの配列に戻るのは迷っています.実はタイトルの意味で、一番大きい数字です.
二つの配列の中からk個の数字を選んで、合わせて構成する数が一番大きいという意味です.もう一つの制限は数字を選ぶ時は配列index順です.
 
最初の配列からi個の数字を取って、最大の数を構成します.同じ道理で第二の配列からk-i個の数字を取って、統合してから結果も一番大きいです.
最外層の循環は0からkまでで、iとk-iが対応する配列の長さを超えたら、このラウンドをスキップする.
次に、それぞれ2つの配列からiビットとk−iビットを取る.
 
配列からi桁を取る数字が一番大きいです.このサブ問題はRemove Duplicate Lettersの考え方に似ています.
欲張りで、スタックを作って、毎回できるだけ中に一番大きな数を詰め込んで、最後にこのスタックは結果です.
nビットの数字を取る必要があると仮定し、各ラウンドがスタックに入る前にまずスタックの状態を維持し、同時に以下の条件を満たすなら、スタックの一番上の要素をイジェクトする.
1.スタックは空ではない
2.スタックトップ要素は現在の要素より小さい.
3.スタックトップがポップアップした後、後に処理されていないサブストリングとスタックのlengthを残してn桁にします.
この例を見て[3,2,1,4,5]n=3.
前三輪は疑問がなくて、倉庫に3、2、1、stack=[3、2、1]を入れます. 
第4ラウンドのサイクルは4対3、2、1の大きさですが、全部は弾けません.3位に足りないので、2つだけ弾いてください.stack=[3、4]です.
最後の5はスタック、スタック=[3、4、5]を入れます.
第三点対応コードには、「stack.length+len-i>n」という条件があります.
 
二つの最大サブシーケンスをそれぞれ取得しました.マージの操作はmerge sortに似ています.
二重の針は、最初は0を指し、大きな針＋を入れて、最後は残りを全部結果に入れます.
同じ数字があるかもしれないので、この時は後ろの数を見て、どれが大きいかを決めます.例えば、[6,1]と[6,7]は[6,7]の6を持つべきです.
 

 1 /**
 2  * @param {number[]} nums1
 3  * @param {number[]} nums2
 4  * @param {number} k
 5  * @return {number[]}
 6  */
 7 var maxNumber = function(nums1, nums2, k) {
 8     var i, m, n, result = [], subNum1, subNum2, mergedNum;
 9     for(i = 0; i <= k ; i++){
10         if(i > nums1.length || k - i > nums2.length) continue;
11         subNum1 = maxSubNum(nums1, i);
12         subNum2 = maxSubNum(nums2, k - i);
13         mergedNum = [];
14         for(m = 0, n = 0; m < subNum1.length && n < subNum2.length;){
15             if(compareNums(subNum1, subNum2, m, n) === 1) mergedNum.push(subNum1[m++]);
16             else mergedNum.push(subNum2[n++]);
17         }
18         while(m < subNum1.length) mergedNum.push(subNum1[m++]);
19         while(n < subNum2.length) mergedNum.push(subNum2[n++]);
20         if(compareNums(mergedNum, result, 0, 0) === 1) result = mergedNum;
21     }
22     return result;
23 
24     function maxSubNum(str, n){
25         var i, stack = [], len = str.length;
26         for(i = 0; i < len; i++){
27             while(stack.length > 0 && stack.length + len - i > n 
28                 && stack[stack.length - 1] < str[i]) stack.pop(); 
29             if(stack.length < n) stack.push(str[i]);
30         }
31         return stack;
32     }
33     /**
34      * @return {number} 1 means num1 is larger than num1, the others return -1.
35      */
36     function compareNums(num1, num2, m, n){
37         if(num1[m] === undefined) return -1;
38         if(num2[n] === undefined) return 1;
39         if(num1[m] > num2[n]) return 1;
40         if(num2[n] > num1[m]) return -1;
41         return compareNums(num1, num2, m + 1, n + 1); //num1[m] === num2[n]
42     }
43 };