Hard

题目描述

给定两个长度分别为 m 和 n 的整数数组 nums1 和 nums2，它们表示两个数字的各个位数。同时给定一个整数 k。

从这两个数字的位数中创建长度为 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]

提示：

  • m == nums1.length
  • n == nums2.length
  • 1 <= m, n <= 500
  • 0 <= nums1[i], nums2[i] <= 9
  • 1 <= k <= m + n
  • nums1 和 nums2 不含前导零

解题思路

解题思路

这道题可以拆解为三个子问题：

  1. 从单个数组中选取指定长度的最大子序列：使用单调栈维护递减序列，当遇到更大的数时，弹出栈顶较小的数（前提是剩余数字足够填满目标长度）。

  2. 合并两个数组得到最大结果：类似归并排序，但比较时需要考虑后续数字。当两个位置的数字相等时，需要比较从当前位置开始的所有后续数字。

  3. 枚举所有可能的分配方案：设从 nums1 中选取 i 个数，从 nums2 中选取 k-i 个数，其中 max(0, k-n) ≤ i ≤ min(k, m)。

算法步骤：

  1. 枚举从 nums1 中选择的数字个数 i
  2. 分别从两个数组中选出长度为 i 和 k-i 的最大子序列
  3. 将两个子序列合并为最大数
  4. 比较所有可能的结果，取最大值

时间复杂度主要集中在合并阶段的字符串比较上，整体为 O(k×(m+n)²)。

代码实现

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size(), n = nums2.size();
        vector<int> result;
        
        for (int i = max(0, k - n); i <= min(k, m); i++) {
            vector<int> sub1 = maxSubsequence(nums1, i);
            vector<int> sub2 = maxSubsequence(nums2, k - i);
            vector<int> merged = merge(sub1, sub2);
            if (isGreater(merged, result)) {
                result = merged;
            }
        }
        
        return result;
    }
    
private:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        if (k == 0) return {};
        vector<int> stack;
        int drop = nums.size() - k;
        
        for (int num : nums) {
            while (!stack.empty() && stack.back() < num && drop > 0) {
                stack.pop_back();
                drop--;
            }
            stack.push_back(num);
        }
        
        return vector<int>(stack.begin(), stack.begin() + k);
    }
    
    vector<int> merge(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        int i = 0, j = 0;
        
        while (i < nums1.size() && j < nums2.size()) {
            if (isGreater(nums1, i, nums2, j)) {
                result.push_back(nums1[i++]);
            } else {
                result.push_back(nums2[j++]);
            }
        }
        
        while (i < nums1.size()) result.push_back(nums1[i++]);
        while (j < nums2.size()) result.push_back(nums2[j++]);
        
        return result;
    }
    
    bool isGreater(vector<int>& nums1, int i, vector<int>& nums2, int j) {
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] > nums2[j]) return true;
            if (nums1[i] < nums2[j]) return false;
            i++;
            j++;
        }
        return i < nums1.size();
    }
    
    bool isGreater(vector<int>& nums1, vector<int>& nums2) {
        return isGreater(nums1, 0, nums2, 0);
    }
};

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        m, n = len(nums1), len(nums2)
        result = []
        
        for i in range(max(0, k - n), min(k, m) + 1):
            sub1 = self.maxSubsequence(nums1, i)
            sub2 = self.maxSubsequence(nums2, k - i)
            merged = self.merge(sub1, sub2)
            if merged > result:
                result = merged
        
        return result
    
    def maxSubsequence(self, nums, k):
        if k == 0:
            return []
        stack = []
        drop = len(nums) - k
        
        for num in nums:
            while stack and stack[-1] < num and drop > 0:
                stack.pop()
                drop -= 1
            stack.append(num)
        
        return stack[:k]
    
    def merge(self, nums1, nums2):
        result = []
        i = j = 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i:] > nums2[j:]:
                result.append(nums1[i])
                i += 1
            else:
                result.append(nums2[j])
                j += 1
        
        result.extend(nums1[i:])
        result.extend(nums2[j:])
        
        return result

public class Solution {
    public int[] MaxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.Length, n = nums2.Length;
        int[] result = new int[0];
        
        for (int i = Math.Max(0, k - n); i <= Math.Min(k, m); i++) {
            int[] sub1 = MaxSubsequence(nums1, i);
            int[] sub2 = MaxSubsequence(nums2, k - i);
            int[] merged = Merge(sub1, sub2);
            if (IsGreater(merged, result)) {
                result = merged;
            }
        }
        
        return result;
    }
    
    private int[] MaxSubsequence(int[] nums, int k) {
        if (k == 0) return new int[0];
        var stack = new List<int>();
        int drop = nums.Length - k;
        
        foreach (int num in nums) {
            while (stack.Count > 0 && stack[stack.Count - 1] < num && drop > 0) {
                stack.RemoveAt(stack.Count - 1);
                drop--;
            }
            stack.Add(num);
        }
        
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = stack[i];
        }
        return result;
    }
    
    private int[] Merge(int[] nums1, int[] nums2) {
        var result = new List<int>();
        int i = 0, j = 0;
        
        while (i < nums1.Length && j < nums2.Length) {
            if (IsGreater(nums1, i, nums2, j)) {
                result.Add(nums1[i++]);
            } else {
                result.Add(nums2[j++]);
            }
        }
        
        while (i < nums1.Length) result.Add(nums1[i++]);
        while (j < nums2.Length) result.Add(nums2[j++]);
        
        return result.ToArray();
    }
    
    private bool IsGreater(int[] nums1, int i, int[] nums2, int j) {
        while (i < nums1.Length && j < nums2.Length) {
            if (nums1[i] > nums2[j]) return true;
            if (nums1[i] < nums2[j]) return false;
            i++;
            j++;
        }
        return i < nums1.Length;
    }
    
    private bool IsGreater(int[] nums1, int[] nums2) {
        return IsGreater(nums1, 0, nums2, 0);
    }
}

var maxNumber = function(nums1, nums2, k) {
    function maxArray(nums, k) {
        let n = nums.length;
        let result = [];
        let drop = n - k;
        
        for (let i = 0; i < n; i++) {
            while (drop > 0 && result.length > 0 && result[result.length - 1] < nums[i]) {
                result.pop();
                drop--;
            }
            result.push(nums[i]);
        }
        
        return result.slice(0, k);
    }
    
    function merge(nums1, nums2) {
        let result = [];
        let i = 0, j = 0;
        
        while (i < nums1.length && j < nums2.length) {
            if (greater(nums1, i, nums2, j)) {
                result.push(nums1[i++]);
            } else {
                result.push(nums2[j++]);
            }
        }
        
        while (i < nums1.length) {
            result.push(nums1[i++]);
        }
        
        while (j < nums2.length) {
            result.push(nums2[j++]);
        }
        
        return result;
    }
    
    function greater(nums1, i, nums2, j) {
        while (i < nums1.length && j < nums2.length && nums1[i] === nums2[j]) {
            i++;
            j++;
        }
        
        return j === nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
    }
    
    function isGreater(arr1, arr2) {
        for (let i = 0; i < Math.min(arr1.length, arr2.length); i++) {
            if (arr1[i] > arr2[i]) return true;
            if (arr1[i] < arr2[i]) return false;
        }
        return arr1.length > arr2.length;
    }
    
    let maxResult = [];
    
    for (let i = Math.max(0, k - nums2.length); i <= Math.min(k, nums1.length); i++) {
        let candidate1 = maxArray(nums1, i);
        let candidate2 = maxArray(nums2, k - i);
        let merged = merge(candidate1, candidate2);
        
        if (maxResult.length === 0 || isGreater(merged, maxResult)) {
            maxResult = merged;
        }
    }
    
    return maxResult;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
最优解法O(k×(m+n)²)O(m+n)

说明：

  • 时间复杂度：需要枚举 k 种分配方案，每种方案中选择子序列的时间为 O(m+n)，合并时的比较操作最坏情况为 O((m+n)²)
  • 空间复杂度：主要用于存储中间结果的子序列和最终结果，为 O(m+n)

相关题目