问题描述
给定长度分别为 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]
解题思路
假设在 nums1 和 nums2 中获取的最大数子序列分别为 s1 和 s2，那么可以 遍历 所有 len(s1)+len(s2)=k 的最大数子序列，然后得到 合并 后的最大数序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 | class Solution:
def maxNumber(
self, nums1: List[int], nums2: List[int], k: int
) -> List[int]:
def max_sub(nums: List[int], k: int) -> List[int]:
# 在 nums 中获取长度为 k 的最大数子序列 (单调栈)
N = len(nums)
s = []
for i in range(N):
while s and nums[i] > s[-1] and len(s) + N - i > k:
s.pop()
if len(s) < k:
s.append(nums[i])
return s
def merge(s1: List[int], s2: List[int]):
# 合并两个子序列能够得到的最大数序列
n1, n2 = len(s1), len(s2)
i1, i2 = 0, 0
s = []
while i1 < n1 and i2 < n2:
if s1[i1:] >= s2[i2:]:
s.append(s1[i1])
i1 += 1
else:
s.append(s2[i2])
i2 += 1
return s + s1[i1:] + s2[i2:]
n1, n2 = len(nums1), len(nums2)
L, R = max(0, k - n2), min(n1, k) # 在nums1中能够取的元素数量范围
ans = [0] * k
for i in range(L, R + 1):
s1 = max_sub(nums1, i)
s2 = max_sub(nums2, k - i)
s3 = merge(s1, s2)
ans = max(ans, s3)
return ans
|