給定長度分別為 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]

代碼

class Solution {public int[] maxNumber(int[] nums1, int[] nums2, int k) {int m=nums1.length,n=nums2.length;int[] res=new int[k];int s=Math.max(0,k-n),end=Math.min(k,m);for(int i=s;i<=end;i++)//遍歷nums1和nums2不同取數情況返回的最大數組，返回最大的結果{int[] cur=merge(getMaxNumber(nums1, i),getMaxNumber(nums2, k-i));if(comp(cur,0,res,0))res=cur;}return res;}public boolean comp(int[] nums1,int p1 ,int[] nums2, int p2) {
//比較兩個序列，如果前面元素都相同，則長度大的較大if(p2>=nums2.length) return true;if(p1>=nums1.length) return false;if(nums1[p1]>nums2[p2]) return true;if(nums1[p1]<nums2[p2]) return false;return comp(nums1, p1+1, nums2, p2+1);}public int[] merge(int[] nums1, int[] nums2) {int n=nums1.length,m=nums2.length;int cur=0,p1=0,p2=0;int []ret=new int[n+m];while (p1<n||p2<m)//合并兩個數組{if(comp(nums1,p1,nums2,p2))ret[cur++]=nums1[p1++];else ret[cur++]=nums2[p2++];}return ret;}public int[] getMaxNumber(int[] nums1, int k) {//單調棧找出單個數組的最大排列int n=nums1.length,rem=n-k,top=-1;int[] stack=new int[k];for(int i=0;i<n;i++){int cur=nums1[i];while (top>=0&&cur>stack[top]&&rem>0){top--;rem--;}if(top<k-1)stack[++top]=cur;else rem--;//可刪除的額度減一，當可刪除的額度用盡，將不能再移除元素（為了保證返回數組的長度）}return stack;}
}