leetcode 321 Create Max Number
greedy的方法，由于有两个数组，我们很自然的想到从数组1中选i个数，数组2中选k-i个数，这样我们只需要遍历max(0, k-数组2长度n) ~ 数组1长度，然后保存合并i和k-i这两个部分之后得到的最大值即可。 那么还剩下这几个问题：
1） 从一个数组中不改变元素顺序地选出i个元素，使他们顺序排列代表的十进制数最大。例：[1,4,3,6,2], i = 3, 结果为[4,6,2]
2） 如何合并数组1的i个元素和数组2的k-i个元素
3） 比较两个数组所代表的十进制数的大小
第一个问题，我们需要使用栈的概念，遍历数组，每次比较栈顶元素与当前元素i，若i比栈顶元素大，则pop栈顶，继续比较，直到栈空或者i比栈顶元素小。注意，我们还需要时刻检测，i之后的元素是否足够补上pop出栈的空缺，若不够则不能再pop。例：[1,4,3,6,2], 当index为3时，栈中有[4,3]，6和3比，大于，弹出3，继续比4，大于，这时候却不能弹出4，因为6后面只有一个数，不够补上pop2次的空缺。
第二个问题，分别用两个index i, j指向数组1和2，比较他们指向的元素，将大的元素放入新的大小为k的数组。注意，如何比较呢？可能指向元素相等，可能某一个数组已经到头了。详细过程在第三个问题列出
第三个问题，如何比较？本题有两个地方需要使用比较，第一个就是主函数中比较不同i值导致的不同长度为k的数组，这个较为简单，因为两个数组长度一致，只需要用两个index，i，j分别遍历两个数组即可，返回nums1[i]和nums2[j]中较大的那一个，若相等则i++,j++，若i=j=k-1还是相等，说明两个数组代表的十进制数相同，返回哪一个都可以。第二个地方就是上一个问题中提到的，比较两个index指向元素的大小，一部分与之前解法相同，元素相等就继续比较后面的元素，不过有一点需要区别的，这里的两个数组可能是不同长度的，所以有可能i或j中某一个指向的位置没有数组元素，即这个数组已经到头了，这种情况，显然就可以返回另一个数组的index指向的元素。
代码如下：
1 class Solution { 2 public int[] maxNumber(int[] nums1, int[] nums2, int k) { 3 int len1 = nums1.length, len2 = nums2.length; 4 int[] res = new int[k]; 5 6 for(int i=0; i<=k; i++){ 7 if((k - i) <= len2 && i <= len1){ 8 int[] tmp = new int[k]; 9 tmp = merge(singleNum(nums1, i), singleNum(nums2, k-i)); 10 if(compare(tmp, 0, res, 0)) 11 res = tmp; 12 } 13 } 14 15 return res; 16 } 17 18 public int[] singleNum(int[] nums, int k){ 19 int len = nums.length; 20 int[] res = new int[k]; 21 int j = 0; 22 23 for(int i=0; i<len; i++){ 24 25 while(len-i+j > k && j > 0 && res[j-1] < nums[i]) 26 j--; 27 if(j < k) 28 res[j++] = nums[i]; 29 } 30 return res; 31 32 } 33 34 public int[] merge(int[] nums1, int[] nums2){ 35 int k = nums1.length + nums2.length; 36 int[] res = new int[k]; 37 38 for(int i=0, j=0, idx = 0; idx < k; idx++){ 39 res[idx] = compare(nums1, i, nums2, j) ? nums1[i++] : nums2[j++]; 40 } 41 return res; 42 43 } 44 45 private boolean compare(int[] nums1, int idx1, int[] nums2, int idx2){ 46 while(idx1 < nums1.length && idx2 < nums2.length && nums1[idx1] == nums2[idx2]){ 47 idx1++; 48 idx2++; 49 } 50 return idx2 == nums2.length || (idx1 < nums1.length && nums1[idx1] > nums2[idx2]); 51 52 } 53 }
leetcode 321 Create Max Number
原文：https://www.cnblogs.com/hwd9654/p/10879605.html