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

## 题目描述

[321. 拼接最大数](https://leetcode-cn.com/problems/create-maximum-number/)

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

## 解题思路

[贪心-分治-栈](https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-6/)

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

剩下要做的就是将这个长度分别为 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`的长度.

```python
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))
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/tan-xin/321-pin-jie-zui-da-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.