問題：

給定長度分別為 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;}// 獲取數組的最大子序列，長度為 lenprivate 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，否則返回 falseprivate 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過程中的一些個人體會總結和借鑒，如有不當、錯誤的地方，請各位大佬批評指正，定當努力改正，如有侵權請聯系作者刪帖。)