# 拼接最大数

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

<p>求满足该条件的最大数。结果返回一个表示该最大数的长度为&nbsp;<code>k</code>&nbsp;的数组。</p>

<p><strong>说明: </strong>请尽可能地优化你算法的时间和空间复杂度。</p>

<p><strong>示例&nbsp;1:</strong></p>

<pre><strong>输入:</strong>
nums1 = <code>[3, 4, 6, 5]</code>
nums2 = <code>[9, 1, 2, 5, 8, 3]</code>
k = <code>5</code>
<strong>输出:</strong>
<code>[9, 8, 6, 5, 3]</code></pre>

<p><strong>示例 2:</strong></p>

<pre><strong>输入:</strong>
nums1 = <code>[6, 7]</code>
nums2 = <code>[6, 0, 4]</code>
k = <code>5</code>
<strong>输出:</strong>
<code>[6, 7, 6, 0, 4]</code></pre>

<p><strong>示例 3:</strong></p>

<pre><strong>输入:</strong>
nums1 = <code>[3, 9]</code>
nums2 = <code>[8, 9]</code>
k = <code>3</code>
<strong>输出:</strong>
<code>[9, 8, 9]</code></pre>


## template

```java

class Solution {

	private 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 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 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 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;
	}
}
```

## 答案

```java

```

## 选项

### A

```java

```

### B

```java

```

### C

```java

```