321. 拼接最大数

Difficulty
Hard
Tags
单调栈
URL
https://leetcode.cn/problems/create-maximum-number/
Star
给定长度分别为 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]
通过次数30,825提交次数73,171

单调栈

思路
题目要求我们用num1和 num2组成k位最大数字，我们可以取num1的可以形成i位最大数字，num2的k - i位最大数字，他们再组成数字就是最大的。
这里有个问题，如何求解一个数组的i位最大数字，例如如何找出[6, 0, 4]最大的两位数字？参考题目
🧧
402. 移掉 K 位数字
需要注意的是，找到 两个子序列后，如何合并？ 因为两个子序列不一定是递增的，所以没法使用常规的方式去合并。需要每次判断 s1[i:] 和 s2[j:]的大小，然后选择一个数值
题解
class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        res = [0] * k
        m, n = len(nums1), len(nums2)
        # 保证 nums1 长度小于 nums2
        if m > n:
            return self.maxNumber(nums2, nums1, k)
        
        # 在 第nums1中取 l 个数字
        for l in range(max(0, k-min(k, n)), min(k, m)+1):
            s1 = self.helper(l, nums1)
            s2 = self.helper(k-l, nums2)
            s = self.merge(s1, s2)
            res = max(res, s)

        return res

            
    
    def helper(self, get_len, nums):
        """ 在 nums 中删除 delet_num 位数字 使得剩下的最大
        """
        delet_num = len(nums) - get_len
        if len(nums) <= delet_num:
            return []

        stack = []
        for i in range(0, len(nums)):
            while stack and delet_num > 0 and nums[i] > stack[-1]:
                delet_num -= 1
                stack.pop()
            stack.append(nums[i])

        while delet_num > 0:
            stack.pop()
            delet_num -= 1

        return stack

    def merge(self, nums1, nums2):
        """ 
        等效于：[max(tmp1, tmp2).pop(0) for _ in range(k)]
        """
        i, j = 0, 0
        res = []
        while i < len(nums1) and j < len(nums2):
            if nums1[i:] > nums2[j:]:
                res.append(nums1[i])
                i += 1
            else:
                res.append(nums2[j])
                j += 1
        
        if i < len(nums1):
            res.extend(nums1[i:])
        elif j < len(nums2):
            res.extend(nums2[j:])
    
        return res