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]
https://leetcode.com/problems/create-maximum-number/
意思看了很久...最后返回一个数组太迷惑了，其实是标题的意思，最大的数字。
题意是从两个数组中选出k个数字，拼在一起组成的数要最大，还有一个限制是选数字的时候要按数组index顺序。
从第一个数组中取i个数字，组成最大的数，同理从第二个数组中取k - i个数字，合并起来之后结果也是最大的。
最外层循环从0到k，如果i和k - i超过了对应数组的长度，跳过这一轮。
然后分别从两个数组中取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比3, 2, 1都大，但不能把它们都弹出，因为不够3位了，只弹出2个，stack = [3, 4]。
最后5放入栈，stack = [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 bigger 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 };
[LeetCode][JavaScript]Create Maximum Number
原文：http://www.cnblogs.com/Liok3187/p/5079343.html