算法题目：拼接最大数：
提示：会使用到了贪心算法，题目难度：比较困难。 贪心算法一般按如下步骤进行：

①建立数学模型来描述问题。 ②把求解的问题分成若干个子问题 。 ③对每个子问题求解，得到子问题的局部最优解。 ④把子问题的解局部最优解合成原来解问题的一个解。

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯 。

算法题目描述

给定长度分别为 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]

示例 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]

java解题参考代码

 public static void main(String[] args) throws ParseException {
        int[] num1 = {3, 9};
        int[] num2 = {8, 9};
        int k = 3;
        int[] i = maxNumber(num1, num2, k);
        System.out.println(i);
    }

    private static int[] maxInNums(int[] nums, int k) {
        int[] max = new int[k];
        int len = nums.length;
        for (int i = 0, j = 0; i < len; ++i) {
            while (j > 0 && k - j < len - i && max[j - 1] < nums[i])
                --j;
            if (j < k)
                max[j++] = nums[i];
        }
        return max;
    }

    private static boolean greater(int[] nums1Max, int i, int[] nums2Max, int j) {
        int lenNums1Max = nums1Max.length;
        int lenNums2Max = nums2Max.length;
        while (i < lenNums1Max && j < lenNums2Max && nums1Max[i] == nums2Max[j]) {
            ++i;
            ++j;
        }
        return j == lenNums2Max || (i < lenNums1Max && nums1Max[i] > nums2Max[j]);
    }

    private static int[] merge(int[] nums1Max, int[] nums2Max) {
        int lenCurRes = nums1Max.length + nums2Max.length;
        int[] curRes = new int[lenCurRes];
        for (int i = 0, j = 0, m = 0; m < lenCurRes; ++m) {
            curRes[m] = greater(nums1Max, i, nums2Max, j) ? nums1Max[i++] : nums2Max[j++];
        }
        return curRes;
    }

    public static int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] res = null;
        for (int i = Math.max(k - nums2.length, 0); i <= Math.min(nums1.length, k); ++i) {
            int[] merge = merge(maxInNums(nums1, i), maxInNums(nums2, k - i));
            res = (res == null || greater(merge, 0, res, 0)) ? merge : res;
        }
        return res;
    }