[321][困难][贪心][分治] 拼接最大数

题目描述

321. 拼接最大数

给定长度分别为 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]

解题思路

贪心-分治-栈

假设我们从第一个数组num1中取了k1个, 从num2中取了k2个, 有k1+k2=k. 而 k1 和 k2 这 两个子问题, 可以参考[402][中等][贪心][栈] 移掉K位数字中的方法来解决. 由于这两个子问题是相互独立的，因此我们只需要分别求解，然后将结果合并即可.

剩下要做的就是将这个长度分别为 k1 和 k2 的数字，合并成一个长度为 k 的数组合并成一个最大的数组。方法为比较两个数组第一个数字, 如果相等, 则继续向后比较, 分出大小之后将对应数组的第一个数字入栈.

这种方法运用了分治思想, 在num1和num2中找各自指定数量的最大子序列是对应的分, 而结果合并成一个数组为治.

具体算法为:

• 从nums1中取$\min(i, \text{len}(\text{nums}_1))$个数形成新的数组A，其中$i$等于 0,1,2, ... k。
• 从nums2中对应取$\min(j, \text{len}(\text{nums}_2))$个数形成新的数组B，其中$j$等于$k - i$。
• 将 A 和 B 按照上面的 merge 方法合并

• 上面我们暴力了 k 种组合情况，我们只需要将 k 种情况取出最大值即可。

时间复杂度为$O(k^2(M+N))$, $k$是要选择的位数, $M$是num1的长度, $N$是num2的长度.

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

        def merge(a, b):
            stack = []
            while a or b:
                bigger = a if a > b else b
                stack.append(bigger[0])
                bigger.pop(0)
            return stack

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