321.拼接最大数

给你两个整数数组 nums1 和 nums2，它们的长度分别为 m 和 n。数组 nums1 和 nums2 分别代表两个数各位上的数字。同时你也会得到一个整数 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]

提示：

• m == nums1.length
• n == nums2.length
• 1 <= m, n <= 500
• 0 <= nums1[i], nums2[i] <= 9
• 1 <= k <= m + n

题解：

class Solution {
    /**
     * k的长度组合数可以为：0+k、1+(k-1)、2+(k-2)、......、n+(k-n)
     * 从多种情况中取出组合最大的一种就是Math.max(0, k - n)，表示数组二的元素个数 >= k，则数组一的元素可以从0开始取
     * 否则再数组二的大小基础上补足
     * nums1：[3, 4, 6, 5]
     * nums2：[9, 1, 2, 5, 8, 3]
     *
     * @param nums1
     * @param nums2
     * @param k
     * @return res
     */
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        int[] res = new int[k];
        for (int i = Math.max(0, k - n); i <= k && i <= m; i++) {
            int[] sub1 = maxSub(nums1, i);
            int[] sub2 = maxSub(nums2, k - i);
            int[] arr = merge(sub1, sub2, k);
            if (compare(arr, 0, res, 0)) {
                res = arr;
            }
        }
        return res;
    }

    /**
     * 求当前序列的最大组合子序列
     * 如果k = 2 + 3，nums1：[6, 5]，nums2：[9, 8, 3]
     *
     * @param arr
     * @param k
     * @return stack
     */
    private int[] maxSub(int[] arr, int k) {
        int[] stack = new int[k];
        // top表示栈顶指针
        int top = 0;
        for (int i = 0; i < arr.length; i++) {
            // arr.length - i表示当前数组中，当前下标到数组末尾还有多少个元素
            // arr.length - i + top > k表示当前下标的元素>=最大组合的栈顶元素，则需要弹出元素
            while (arr.length - i + top > k && top > 0 && arr[i] > stack[top - 1]) {
                top--;
            }
            // 如果当前栈顶指向的元素下标小于k，则top指向下一个栈顶，元素入栈
            if (top < k) {
                stack[top++] = arr[i];
            }
        }
        return stack;
    }

    /**
     * 合并两个序列成为一个最大序列
     * nums1 [6, 5]
     * nums2 [9, 8, 3]
     * 合并后 [9, 8, 6, 5, 3]
     * 双指针排序
     *
     * @param nums1
     * @param nums2
     * @param k
     * @return res
     */
    private int[] merge(int[] nums1, int[] nums2, int k) {
        int[] res = new int[k];
        /**
         * i, j都是num1和num2分别对应的指针下标
         * index是结果数组的下标
         */
        for (int i = 0, j = 0, index = 0; index < k; index++) {
            if (compare(nums1, i, nums2, j)) {
                res[index] = nums1[i++];
            } else {
                res[index] = nums2[j++];
            }
        }
        return res;
    }

    /**
     * 比较两个数组对应位置元素的大小，相等就跳过，不相等就比较
     *
     * @param nums1
     * @param i
     * @param nums2
     * @param j
     * @return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j])
     */
    private boolean compare(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]);
    }
}