问题：
给定长度分别为 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 实现拼接最大数的示例代码：
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int m = nums1.length;
int n = nums2.length;
int[] result = new int[k];
Arrays.fill(result, -1);
// 从数组 nums1 中选择 i 个数字，从数组 nums2 中选择 k - i 个数字
for (int i = Math.max(0, k - n); i <= Math.min(k, m); i++) {
int[] subsequence1 = getMaxSubsequence(nums1, i);
int[] subsequence2 = getMaxSubsequence(nums2, k - i);
int[] merged = merge(subsequence1, subsequence2);
if (isGreater(merged, result, 0, 0)) {
System.arraycopy(merged, 0, result, 0, k);
}
}
return result;
}
// 获取数组的最大子序列，长度为 len
private int[] getMaxSubsequence(int[] nums, int len) {
int[] stack = new int[len];
int top = -1;
for (int i = 0; i < nums.length; i++) {
while (top >= 0 && stack[top] < nums[i] && top + nums.length - i > len) {
top--;
}
if (top < len - 1) {
stack[++top] = nums[i];
}
}
return stack;
}
// 合并两个子序列
private int[] merge(int[] subsequence1, int[] subsequence2) {
int[] merged = new int[subsequence1.length + subsequence2.length];
int i = 0, j = 0, k = 0;
while (i < subsequence1.length && j < subsequence2.length) {
if (subsequence1[i] > subsequence2[j]) {
merged[k++] = subsequence1[i++];
} else if (subsequence1[i] < subsequence2[j]) {
merged[k++] = subsequence2[j++];
} else {
int p = i + 1, q = j + 1;
while (p < subsequence1.length && q < subsequence2.length && subsequence1[p] == subsequence2[q]) {
p++;
q++;
}
if (q == subsequence2.length || (p < subsequence1.length && subsequence1[p] > subsequence2[q])) {
merged[k++] = subsequence1[i++];
} else {
merged[k++] = subsequence2[j++];
}
}
}
while (i < subsequence1.length) {
merged[k++] = subsequence1[i++];
}
while (j < subsequence2.length) {
merged[k++] = subsequence2[j++];
}
return merged;
}
// 比较两个整数数组，如果 num1 更大，则返回 true，否则返回 false
private boolean isGreater(int[] num1, int[] num2, int index1, int index2) {
while (index1 < num1.length && index2 < num2.length) {
if (num1[index1]!= num2[index2]) {
return num1[index1] > num2[index2];
}
index1++;
index2++;
}
return index1!= num1.length;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums1 = {3, 4, 6, 5};
int[] nums2 = {9, 1, 2, 5, 8, 3};
int k = 5;
int[] result = solution.maxNumber(nums1, nums2, k);
System.out.println(Arrays.toString(result));
}
}上述示例代码中，定义了一个名为'Solution'的类。'maxNumber'方法用于拼接两个数组的最大数，通过遍历从两个数组中选择不同长度的数字，得到最大子序列，并利用辅助方法'merge'、'getMaxSubsequence'和'isGreater'进行合并、获取子序列和比较。'merge'方法用于合并两个数组，利用双指针进行比较和合并。'getMaxSubsequence'方法用于获取最大子序列，通过单调栈保存当前最大数字。'isGreater'方法用于比较两个整数数组的大小。
(文章为作者在学习java过程中的一些个人体会总结和借鉴，如有不当、错误的地方，请各位大佬批评指正，定当努力改正，如有侵权请联系作者删帖。)