题目链接
思路：单调栈
这个题目其实就是好几个问题绑在了一起，现在我们来一层层拆开它。
首先，要挑选出k个，那么可以从第一个数组里面挑选0个、1个、2个、…k个，对应的，从第二个数组里面挑选 k个、k-1、k-2、…0个，那么挑选这些元素有什么规则，题目是要求他们拼凑出来的数组最大，那么他们自身出来的肯定就要最大。

问题1.在nums数组中，挑选k个数，并且要保证相对顺序，如何使得挑选出来的数字组成的数组最大。
思路：单调栈
定义一个栈，这个栈从栈底到栈顶，依次减小，即栈顶永远是栈内最小的。，然后去掉的元素个数是有限制的。

问题一解决。

问题二：从nums1中挑选了x个，从nums2中挑选了k-x个，得到数组后，如果组合才会使得最大。
思路：就是当前元素谁大，谁就放前面，一样大就比后面的数，谁大，就把当前元素放前面，如果后面没有数，谁短谁就小。

问题二解决。

问题二持续更新答案。
最后就是答案。
代码：

class Solution {public int[] maxNumber(int[] nums1, int[] nums2, int k) {int len1 = nums1.length;int len2 = nums2.length;int[] res = new int[k];for(int tarLen1 = 0;tarLen1 <=k;tarLen1++){if(tarLen1>len1){break;}if(k-tarLen1>len2){continue;}//从nums1中需要被移除的元素的个数int count1 = len1 - tarLen1;//从nums2中需要被移除的元素的个数int count2 = len2 - (k - tarLen1);//问题一对应代码，这里是从nums1中移除count1个元素，使得cs1最大int[] cs1 = getMaxString(nums1, count1, len1);int[] cs2 = getMaxString(nums2, count2, len2);int[] getMaxCharArrres = new int[cs1.length + cs2.length];//这里是问题二对应的代码，cs1  cs2即使挑选出来的最大数组，然后怎么组合int[] temMax = getMaxCharArr(cs1,cs2,getMaxCharArrres,0,0,0);//更新答案for(int i = 0;i < k;i++){if(res[i]<temMax[i]){res = temMax;break;}else if(res[i]>temMax[i]){break;}}}return res;}//两个数组中合并成一个最大的数组----问题二public int[] getMaxCharArr(int[] cs1, int[] cs2,int[] res,int i1, int i2,int index){if(index == cs1.length + cs2.length ){return res;}if(i1 == cs1.length){while (i2!=cs2.length){res[index++] = cs2[i2++];}return res;}if(i2 == cs2.length){while (i1!=cs1.length){res[index++] = cs1[i1++];}return res;}if(compare(cs1,cs2,i1,i2)){res[index++] = cs1[i1++];}else {res[index++] = cs2[i2++];}return getMaxCharArr(cs1,cs2,res,i1,i2,index);}//移除k个数字使得最大---问题一public int[] getMaxString(int[] nums,int k, int len){//逻辑栈int[] stack = new int[len];//最后返回的答案int[] res = new int[len-k];int top = -1;int i = 0;for(;i<len;i++){int cur = nums[i];//如果栈顶比当前元素小，那么出栈while (top!=-1 && k>0 && stack[top]<cur){top--;k--;}if(k==0){break;}//当前元素入栈stack[++top] = cur;}while (k!=0){top--;k--;}//将后面的元素入栈while (i<len){stack[++top] = nums[i++];}i = 0;//将前面的元素入答案while (i<res.length){res[i] = stack[i];i++;}return res;}//对应两个数组谁大   返回true就是cs1大public boolean compare(int[] cs1,int[] cs2,int index1, int index2){//谁短谁小if(index1 == cs1.length){return false;}if(index2 == cs2.length){return true;}while (index1 < cs1.length && index2 < cs2.length){int d = cs1[index1] - cs2[index2];if(d!=0){return d > 0 ? true : false;}index1++;index2++;}return index1 == cs1.length? false : true;}
}