本文共 2477 字，大约阅读时间需要 8 分钟。
给定长度分别为 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]参考了官方题解的缝合怪代码，注意点在于找出数组最大k位按序子数组的部分运用了单调栈
class Solution { public: vector maxNumber(vector & nums1, vector & nums2, int k) { int m = nums1.size(), n = nums2.size(); vector maxSubsequence(k, 0); int start = max(0, k - n), end = min(k, m); for (int i = start; i <= end; i++) { vector subsequence1(MaxSubsequence(nums1, i)); vector subsequence2(MaxSubsequence(nums2, k - i)); vector curMaxSubsequence(merge(subsequence1, subsequence2)); if (compare(curMaxSubsequence, 0, maxSubsequence, 0)) { maxSubsequence.swap(curMaxSubsequence); } } return maxSubsequence; } //从nums中的到保持顺序的a位数组 vector MaxSubsequence(vector & nums, int k) { int length = nums.size(); vector stack(k, 0); int top = -1; //remain用于逆向统计栈内已有的但顺序超出k的元素，每次入栈的时候，若一个数入栈的位置在k位右侧，则remain-- 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 merge(vector sub1,vector sub2){ int n = sub1.size(),m = sub2.size(); if(n == 0){ return sub2; } if(m == 0){ return sub1; } int mergedLength = n + m; vector res(mergedLength); int index1 = 0,index2 = 0; for(int i = 0;i 转载地址：http://ndqmz.baihongyu.com/