题目
给定长度分别为 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]解答
- 单调栈
为了找到长度为 kkk 的最大数，需要从两个数组中分别选出最大的子序列，这两个子序列的长度之和为 kkk，然后将这两个子序列合并得到最大数。两个子序列的长度最小为 000，最大不能超过 kkk 且不能超过对应的数组长度。
令数组 $\textit{nums}_1$ 的长度为 m，数组 $\textit{nums}_2$的长度为 n，则需要从数组 $\textit{nums}_1$中选出长度为 x 的子序列，以及从数组$\textit{nums}_2$ 中选出长度为 yyy 的子序列，其中$x+y=k$，且满足$0 \le x \le m$和$0 \le y \le n$。需要遍历所有可能的 $x$ 和 $y$ 的值，对于每一组$x$ 和 $y$ 的值，得到最大数。在整个过程中维护可以通过拼接得到的最大数。
对于每一组 $x$ 和 $y$ 的值，得到最大数的过程分成两步，第一步是分别从两个数组中得到指定长度的最大子序列，第二步是将两个最大子序列合并。
第一步可以通过单调栈实现。单调栈满足从栈底到栈顶的元素单调递减，从左到右遍历数组，遍历过程中维护单调栈内的元素，需要保证遍历结束之后单调栈内的元素个数等于指定的最大子序列的长度。遍历结束之后，将从栈底到栈顶的元素依次拼接，即得到最大子序列。
第二步需要自定义比较方法。首先比较两个子序列的当前元素，如果两个当前元素不同，则选其中较大的元素作为下一个合并的元素，否则需要比较后面的所有元素才能决定选哪个元素作为下一个合并的元素。
在下面的代码中，单调栈使用数组实现，数组最左侧为栈底。使用数组实现，可以直接从左到右遍历数组得到最大子序列。
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int m = nums1.size(), n = nums2.size();
vector<int> maxSubsequence(k, 0); // 存储最大的子序列结果
int start = max(0, k - n), end = min(k, m); // 确定子序列长度的起始和结束范围
for (int i = start; i <= end; i++) {
vector<int> subsequence1(MaxSubsequence(nums1, i)); // 从nums1中取i个数字组成的最大子序列
vector<int> subsequence2(MaxSubsequence(nums2, k - i)); // 从nums2中取k-i个数字组成的最大子序列
vector<int> curMaxSubsequence(merge(subsequence1, subsequence2)); // 合并两个子序列得到当前最大结果
if (compare(curMaxSubsequence, 0, maxSubsequence, 0) > 0) {
maxSubsequence.swap(curMaxSubsequence); // 如果当前最大结果更大，则更新maxSubsequence
}
}
return maxSubsequence; // 返回最终的最大子序列结果
}
vector<int> MaxSubsequence(vector<int>& nums, int k) {
int length = nums.size();
vector<int> stack(k, 0); // 使用stack来构建最大子序列
int top = -1;
int remain = length - k; // 记录还需要丢弃的数字个数
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; // 返回最终构建的最大子序列
}
vector<int> merge(vector<int>& subsequence1, vector<int>& subsequence2) {
int x = subsequence1.size(), y = subsequence2.size();
if (x == 0) {
return subsequence2; // 如果subsequence1为空，则直接返回subsequence2
}
if (y == 0) {
return subsequence1; // 如果subsequence2为空，则直接返回subsequence1
}
int mergeLength = x + y;
vector<int> merged(mergeLength); // 合并结果的数组
int index1 = 0, index2 = 0;
for (int i = 0; i < mergeLength; i++) {
if (compare(subsequence1, index1, subsequence2, index2) > 0) {
merged[i] = subsequence1[index1++]; // 如果subsequence1的当前元素较大，则加入到合并结果中
} else {
merged[i] = subsequence2[index2++]; // 否则，加入subsequence2的当前元素到合并结果中
}
}
return merged; // 返回合并的结果
}
int compare(vector<int>& subsequence1, int index1, vector<int>& subsequence2, int index2) {
int x = subsequence1.size(), y = subsequence2.size();
while (index1 < x && index2 < y) {
int difference = subsequence1[index1] - subsequence2[index2];
if (difference != 0) {
return difference; // 比较两个子序列当前位置的元素，不相等则直接返回差值
}
index1++; // 继续比较下一个位置
index2++;
}
return (x - index1) - (y - index2); // 返回长度较长的子序列对应位置多出的元素个数
}
};作者：力扣官方题解
链接：https://leetcode.cn/problems/create-maximum-number/solutions/505931/pin-jie-zui-da-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。