321. 拼接最大数

难度困难

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

# 贪心 + 单调栈

由题可知，需要从 $nums1$ 与 $nums2$ 中选择一共选择 $k$ 个数字，拼接成一个新的最大的数

即从 $nums1$ 中选择 $x$ 个最大数 $l$ ，从 $nums2$ 中选择 $y$ 个最大数 $r$ ，然后合并二者形成整体最大的数。

$x + y = k$

可以枚举 $x$ ，使得合并后对答案的贡献值最大。

若选出了 $l$ 与 $r$ ，如何合并呢？贪心。设 $n = l.length$ ， $m=r.length$

若 $i>=n \;\&\&\;j>=m$ ，退出循环
若 $i<n \;\&\&\;j>=m$ ，剩余全为 $l[i]$ ，选择 $l[i]$
若 $i>=n \;\&\&\;j<m$ ，剩余全为 $r[i]$ ，选择 $r[i]$
若 $l[i] < r[j]$ ，那么选择 $r[i]$
若 $l[i] > r[j]$ ，那么选择 $l[j]$
若 $l[i] == r[j]$ ，需要额外的讨论

可以看 $l[i+1]$ 与 $r[j+1]$ 的关系，回到了上述讨论的情况

如何在选择 $nums1$ 中选择 $x$ 个最大数 $l$ 呢？可以转化为删除 $n - x$ 个元素得到的最大值，其实就是 402. 移掉 K 位数字

	class Solution {
	int[] ans;

	public int[] maxNumber(int[] nums1, int[] nums2, int k) {
	int n = nums1.length;
	int m = nums2.length;
	ans = new int[k];
	// 枚举 x
	int max = Math.min(n, k);
	for (int x = Math.max(0, k - m); x <= max; x++) {
	int[] l = getSubMaxNumber(nums1, x);
	int[] r = getSubMaxNumber(nums2, k - x);
	merge(l, r);
	}
	return ans;
	}

	private void merge(int[] l, int[] r) {
	int n = l.length;
	int m = r.length;
	boolean flag = false;
	for (int i = 0, j = 0, idx = 0; i < n \|\| j < m; idx++) {
	//l[i] > r[j]
	if (compare(i, j, l, r)) {
	// 只有 ans 没有被修改过
	if (!flag && l[i] < ans[idx]) {
	return;
	}
	if (l[i] > ans[idx]) {
	flag = true;
	}
	ans[idx] = l[i++];
	} else {
	// 只有 ans 没有被修改过
	if (!flag && r[j] < ans[idx]) {
	return;
	}
	if (r[j] > ans[idx]) {
	flag = true;
	}
	ans[idx] = r[j++];
	}
	}
	}

	private boolean compare(int i, int j, int[] l, int[] r) {
	int n = l.length;
	int m = r.length;
	if (i >= n && j >= m) {
	// 都可以
	return false;
	} else if (i < n && j >= m) {
	return true;
	} else if (i >= n) {
	return false;
	}
	if (l[i] > r[j]) {
	return true;
	} else if (l[i] < r[j]) {
	return false;
	}
	// 相等，继续往下比较
	return compare(i + 1, j + 1, l, r);
	}


	private int[] getSubMaxNumber(int[] nums, int x) {
	int n = nums.length;
	// 将选择变成删除
	int k = n - x;
	// 调调递减栈
	Deque<Integer> st = new ArrayDeque<>();
	for (int num : nums) {
	// 若 num 与栈顶元素相等，那么也不能移除，因为要让数「尽可能大」，所需能保留就保留
	// - [5, 5, 1] 选择 2 个数，必然是 [5, 5] 而不是 [5, 1]
	while (k > 0 && !st.isEmpty() && st.peekFirst() < num) {
	st.pollFirst();
	k--;
	}
	st.addFirst(num);
	}
	int[] ans = new int[x];
	// 若 k 有剩余，去除最后的 k 个
	for (int i = 0; i < x; i++) {
	ans[i] = st.pollLast();
	}
	return ans;
	}
	}

复杂度分析

时间复杂度： $O(k(m +n+k^2))$ ，其中 $n$ 与 $m$ 分别是 $nums1$ 和 $nums2$ 的长度， $k$ 是拼接的最大长度

合并 $2$ 个子序列，需要 $k$ 次合并，每次合并需要比较，最坏情况下需要比较 $k$ 次，即 $k^2$ 。
空间复杂度： $O(k)$

字典序最小

栈单调栈贪心困难

# 贪心 + 单调栈

移掉 K 位数字

数组的最大公因数排序