golang 解法, 执行用时: 12 ms, 内存消耗: 6.7 MB, 提交时间: 2023-07-23 11:02:23

func maxSubsequence(a []int, k int) (s []int) {
    for i, v := range a {
        for len(s) > 0 && len(s)+len(a)-1-i >= k && v > s[len(s)-1] {
            s = s[:len(s)-1]
        }
        if len(s) < k {
            s = append(s, v)
        }
    }
    return
}

func lexicographicalLess(a, b []int) bool {
    for i := 0; i < len(a) && i < len(b); i++ {
        if a[i] != b[i] {
            return a[i] < b[i]
        }
    }
    return len(a) < len(b)
}

func merge(a, b []int) []int {
    merged := make([]int, len(a)+len(b))
    for i := range merged {
        if lexicographicalLess(a, b) {
            merged[i], b = b[0], b[1:]
        } else {
            merged[i], a = a[0], a[1:]
        }
    }
    return merged
}

func maxNumber(nums1, nums2 []int, k int) (res []int) {
    start := 0
    if k > len(nums2) {
        start = k - len(nums2)
    }
    for i := start; i <= k && i <= len(nums1); i++ {
        s1 := maxSubsequence(nums1, i)
        s2 := maxSubsequence(nums2, k-i)
        merged := merge(s1, s2)
        if lexicographicalLess(res, merged) {
            res = merged
        }
    }
    return
}

javascript 解法, 执行用时: 84 ms, 内存消耗: 47.1 MB, 提交时间: 2023-07-23 11:00:50

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[]}
 */
var maxNumber = function(nums1, nums2, k) {
    var r = Array(k).fill(0), end = Math.min(k, nums1.length)
    for(var i = Math.max(0, k - nums2.length); i <= end; i++) 
            r = max(r, merge(maxSubsequence(nums1, i), maxSubsequence(nums2, k - i)))
    return r
};
var maxSubsequence = (nums, k) => {
    var mStack = [], len = nums.length, top = -1, last = len - k
    for(var i = 0; i < len; i++) {
        while (top > -1 && nums[i] > mStack[top] && last > 0) top--, last--
        top < k - 1 ? mStack[++top] = nums[i] : last--
    }
    return mStack
}
var merge = (nums1, nums2) => {
    var p1 = p2 = 0, r = [], len1 = nums1.length, len2 = nums2.length
    while (p1 < len1 || p2 < len2) {
        if (p2 >= len2 || nums1[p1] > nums2[p2]) r.push(nums1[p1++])
        else if (nums1[p1] === nums2[p2]) {
            var _p1 = p1, _p2 = p2
            while(_p1 < len1 && nums1[++_p1] === nums2[++_p2]) {}
            r.push(_p2 >= len2 || nums1[_p1] > nums2[_p2] ? nums1[p1++] : nums2[p2++])
        } else r.push(nums2[p2++])
    }
    return r 
}
var max = (nums1, nums2, p1 = p2 = -1, len1 = nums1.length) => {
    while(p1 < len1 && nums1[++p1] === nums2[++p2]) {}
    return nums2[p2] > nums1[p1] ? nums2 : nums1
}

cpp 解法, 执行用时: 40 ms, 内存消耗: 31.9 MB, 提交时间: 2023-07-23 10:59:26

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> res(k, 0);
        int n = nums1.size(), m = nums2.size();
        // 假设有最大子序列中有s个元素来自nums1，对所有可能的s值遍历
        for (int s=max(0, k-m); s<=min(k, n); s++){
            vector<int> temp;
            int i = 0, j = 0;
            // nums1中长度为s的最大子序列
            vector<int> temp1 = maxKsequence(nums1, s);
            // nums2中长度为k-s的最大子序列
            vector<int> temp2 = maxKsequence(nums2, k-s);
            // 对两个子序列进行归并
            // lexicographical_compare：比较两个序列的字典序大小
            auto iter1 = temp1.begin(), iter2 = temp2.begin();
            while (iter1 != temp1.end() || iter2 != temp2.end()){
                temp.push_back(lexicographical_compare(iter1, temp1.end(), iter2, temp2.end()) ? *iter2++ : *iter1++);
            }
            // 如果归并后的最大子序列大于目前已找到的最大子序列，则更新解
            res = lexicographical_compare(res.begin(), res.end(), temp.begin(), temp.end()) ? temp : res;
        }
        return res;
    }

    // 求数组v的长度为k的最大子序列
    vector<int> maxKsequence(vector<int> v, int k){
        int n = v.size();
        if (n <= k)
            return v;
        vector<int> res;
        int pop = n-k;
        for (int i=0; i<n; i++){
            while(!res.empty() && v[i]>res.back() && pop-->0)
                res.pop_back();
            res.push_back(v[i]);
        }
        res.resize(k);
        return res;
    }
};

python3 解法, 执行用时: 180 ms, 内存消耗: 16.3 MB, 提交时间: 2023-07-23 10:57:23

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        def pick_max(nums: List[int], k: int):
            stack = []
            drop = len(nums) - k
            for num in nums:
                while drop and stack and stack[-1] < num:
                    stack.pop()
                    drop -= 1
                stack.append(num)
            return stack[:k]

        def merge(A: int, B: int):
            ans = []
            while A or B:
                bigger = A if A > B else B
                ans.append(bigger[0])
                bigger.pop(0)
            return ans

        return max(merge(pick_max(nums1, i), pick_max(nums2, k-i)) for i in range(k+1) if i <= len(nums1) and k-i <= len(nums2))