数组中求一个长度为k的子序列，使得该子序列按顺序组成的十进制数最大

    public static int[] maxSubsequence(int[] nums, int k) {
        int length = nums.length;
        int[] stack = new int[k];
        int top = -1;//栈顶指针
        int remain = length - k;//remain表示数组中可以删除的元素个数
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            while (top >= 0 && stack[top] < num && remain > 0) {
                top--;
                remain--;
            }
            if (top < k - 1) {
                stack[++top] = num;
            } else {
                remain--;
            }
        }
        return stack;
    }

必须通过remain记录可以删除的元素个数，以此维护顺序性
反例：9, 1, 2, 5, 8, 3,1,4,9   k=3

应用 ：leetcode 拼接最大数

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/create-maximum-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

通过nums1中取x个元素的最大子序列 nums2中取y个元素的最大子序列 x+y==k; x取值范围为[max(0,k-n),min(k,m)]
将所有符合情况的（x,y）枚举，对于获得的两个最大子序列，进行合并（二路归并），归并完之后得到一个数组，需要将该数组与所有的(x,y)获得的结果数组进行比较，比较的规则类似，所以通过一个数组比较方法进行比较

public int compare(int[] nums1,int index1,int[] nums2,int index2){
    int n=nums1.length;int m=nums2.length;
    while(index1<n&&index2<m){
        if(nums1[index1]!=nums2[index2]){
            return nums1[index1]-nums2[index2];
        }
        //否则相等继续比较下一个元素
        index1=index++;
        index2=index2++;
    }
    return (n-index1)-(m-index2);//更长的数组更大
}

将两个数组最大子序列合并成一个最大的数组序列 合并的规则是对于每一个元素选择剩余序列更大的位置进行合并

    public int[] merge(int[] nums1,int[] nums2){
        int n=nums1.length;int m=nums2.length;

        if(n==0){
            return nums2;
        }
        if(m==0){
            return nums1;
        }

        int index=0;
        int[] res=new int[m+n];
        int i=0,j=0;

        //合并的规则是每次都从剩余的序列中选择最大的数组进行元素合并
        for(int k=0;k<(m+n);k++){
            if(compare(nums1,i,nums2,j)>0){
                res[index++]=nums1[i++];
            }else{
                res[index++]=nums2[j++];
            }
        }

        return res;
    }

Java

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int n=nums1.length;int m=nums2.length;
        int start=Math.max(0,k-m);int end=Math.min(k,n);
        //创建结果
        int[] res=new int[k];
        for(int i=start;i<=end;i++){
            int j=k-i;
            int[] stack1=getMaxSub(nums1,i);
            int[] stack2=getMaxSub(nums2,j);

            int[] mergeRes=merge(stack1,stack2);        
            if(compare(mergeRes,0,res,0)>0){
                System.arraycopy(mergeRes,0,res,0,k);
            }
        }
        return res;
    }

    public int compare(int[] nums1,int index1,int[] nums2,int index2){
        int n=nums1.length;int m=nums2.length;
        while(index1<n&&index2<m){
            if(nums1[index1]!=nums2[index2]){
                return nums1[index1]-nums2[index2];
            }
            index1++;index2++;
        }
        return (n-index1)-(m-index2);
    }

    public int[] getMaxSub(int[] nums,int k){
        int n=nums.length;
        int[] stack=new int[k];
        int top=-1;
        int remain=n-k;
        for(int i=0;i<n;i++){
            int num=nums[i];
            while(top>=0&&stack[top]<num&&remain>0){
                top--;
                remain--;
            }
            if(top<k-1){
                stack[++top]=num;
            }else{
                remain--;
            }
        }
        return stack;
    }

    public int[] merge(int[] nums1,int[] nums2){
        int n=nums1.length;int m=nums2.length;

        if(n==0){
            return nums2;
        }
        if(m==0){
            return nums1;
        }

        int index=0;
        int[] res=new int[m+n];
        int i=0,j=0;
        // while(i<n&&j<m){
        //     if(nums1[i]<nums2[j]){
        //         res[index++]=nums2[j++];
        //     }else if(nums1[i]>nums2[j]){
        //         res[index++]=nums1[i++];
        //     }else{
        //         //如果两个相等，优先合并剩余元素更长的数组
        //         if((n-i)>(m-j)){
        //             res[index++]=nums1[i++];
        //         }else{
        //             res[index++]=nums2[j++];
        //         }
        //     }
        // }
        // while(i<n){
        //     res[index++]=nums1[i++];
        // }
        // while(j<m){
        //     res[index++]=nums2[j++];
        // }

        //合并的规则是每次都从剩余的序列中选择最大的数组进行元素合并
        for(int k=0;k<(m+n);k++){
            if(compare(nums1,i,nums2,j)>0){
                res[index++]=nums1[i++];
            }else{
                res[index++]=nums2[j++];
            }
        }

        return res;
    }

}