拼接最大数

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1:

输入:

nums1 = [3, 4, 6, 5]

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

k = 5

输出:

[9, 8, 6, 5, 3]

示例 2:

输入:

nums1 = [6, 7]

nums2 = [6, 0, 4]

k = 5

输出:

[6, 7, 6, 0, 4]

示例 3:

输入:

nums1 = [3, 9]

nums2 = [8, 9]

k = 3

输出:

[9, 8, 9]

首先采用分治法的思路，我们知道这K个数字中，必然有i个数组来自nums1，而剩下的k-i个数字必然来自nums2。那么问题变成从nums1中获取i个数，这i个数构成的数字最大，且这i个数字的相对位置不变。再从nums2中获取k-i个数，这k-i个数构成的数字最大，且这k-i个数字的相对位置不变。

那么我们如何将这两个结果合并起来获得我们最终的结果呢？这里很像归并算法的merge过程，我们从两个数组的开头获取最大的值加进来呗。那如果出现相同的值怎么办？那么继续比较，直到遇到第一个不相同的数字，然后选择数字较大的那个数组。

public class Solution {
private int[] max(int[] nums, int k) {
int[] max = new int[k];
for(int i=0, j=0; i0 && k-j<nums.length-i && max[j-1]<nums[i]) j--;
if (j<k) max[j++] = nums[i];
}
return max;
}

 private int\[\] merge(int\[\] nums1, int\[\] nums2) {  
     int\[\] merged = new int\[nums1.length+nums2.length\];  
     for(int i=0, j=0, m=0; m<merged.length; m++) {  
         merged\[m\] = greater(nums1, i, nums2, j) ? nums1\[i++\] : nums2\[j++\];  
     }  
     return merged;  
 }

 private boolean greater(int\[\] nums1, int i, int\[\] nums2, int j) {  
     while (i<nums1.length && j<nums2.length && nums1\[i\]==nums2\[j\]) {  
         i++;  
         j++;  
     }  
     return j==nums2.length || (i<nums1.length && nums1\[i\]>nums2\[j\]);  
 }

 public int\[\] maxNumber(int\[\] nums1, int\[\] nums2, int k) {  
     int\[\] max = null;  
     for(int i=Math.max(k-nums2.length, 0); i<=Math.min(nums1.length, k); i++) {  
         int\[\] merged = merge(max(nums1, i), max(nums2, k-i));  
         if (max == null || greater(merged, 0, max, 0)) max = merged;  
     }  
     return max;  
 }  

}