难度: Hard
给你两个整数数组 nums1 和 nums2，它们的长度分别为 m 和 n。数组 nums1 和 nums2 分别代表两个数各位上的数字。同时你也会得到一个整数 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.lengthn == nums2.length1 <= m, n <= 5000 <= nums1[i], nums2[i] <= 91 <= k <= m + n运行时间: 72 ms
内存: 16.8 MB
class Solution:
def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
m,n=len(nums1),len(nums2)
delete_order1=[]
delete_order2=[]
stack1=[]
stack2=[]
for i in range(len(nums1)):
if not stack1 or nums1[i]<=nums1[stack1[-1]]:
stack1.append(i)
else:
while stack1 and nums1[i]>nums1[stack1[-1]]:
t=stack1.pop()
delete_order1.append(t)
stack1.append(i)
for i in stack1[::-1]:
delete_order1.append(i)
for i in range(len(nums2)):
if not stack2 or nums2[i]<=nums2[stack2[-1]]:
stack2.append(i)
else:
while stack2 and nums2[i]>nums2[stack2[-1]]:
t=stack2.pop()
delete_order2.append(t)
stack2.append(i)
for i in stack2[::-1]:
delete_order2.append(i)
delete_order1=delete_order1[::-1]
delete_order2=delete_order2[::-1]
generate1=[]
generate2=[]
cur=''
lst1=[]
lst2=[]
for i in delete_order1:
t=bisect_left(lst1,i)
lst1[t:t]=[i]
cur=cur[:t]+str(nums1[i])+cur[t:]
generate1.append(cur)
cur=''
for i in delete_order2:
t=bisect_left(lst2,i)
lst2[t:t]=[i]
cur=cur[:t]+str(nums2[i])+cur[t:]
generate2.append(cur)
ans=[]
def join_max(s1,s2):
i=0
j=0
ans=''
while i<len(s1) or j<len(s2):
if i==len(s1):
ans+=s2[j:]
return ans
if j==len(s2):
ans+=s1[i:]
return ans
if (s1[i:])<=(s2[j:]):
ans+=s2[j]
j+=1
else:
ans+=s1[i]
i+=1
return ans
cmax=0
for i in range(max(0,k-n),min(m,k)+1):
if i==0 :
cmax=max(cmax,int(generate2[k-1]))
elif i==k:
cmax=max(cmax,int(generate1[k-1]))
else:
s1=generate1[i-1]
s2=generate2[k-i-1]
tmp=join_max(s1,s2)
cmax=max(cmax,int(tmp))
return list(map(int,list(str(cmax))))
题解思路分为几个步骤： 1. 对于 nums1 和 nums2 分别生成所有可能的子序列（通过删除元素）的非降序排列。 2. 然后对于每个可能的 i（i 代表从 nums1 中选择的元素数量，k-i 代表从 nums2 中选择的元素数量），将 nums1 中的前 i 个元素和 nums2 中的前 k-i 个元素合并成最大的数。 3. 比较所有合并后的数，找到最大的那个。
时间复杂度: O(m^2 + n^2 + k*min(m,k))
空间复杂度: O(m^2 + n^2 + k)
class Solution:
def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
m,n=len(nums1),len(nums2)
delete_order1=[]
delete_order2=[]
stack1=[]
stack2=[]
# 使用单调栈来生成 nums1 的所有可能的子序列的非降序排列
for i in range(len(nums1)):
if not stack1 or nums1[i]<=nums1[stack1[-1]]:
stack1.append(i)
else:
while stack1 and nums1[i]>nums1[stack1[-1]]:
t=stack1.pop()
delete_order1.append(t)
stack1.append(i)
for i in stack1[::-1]:
delete_order1.append(i)
# 使用单调栈来生成 nums2 的所有可能的子序列的非降序排列
for i in range(len(nums2)):
if not stack2 or nums2[i]<=nums2[stack2[-1]]:
stack2.append(i)
else:
while stack2 and nums2[i]>nums2[stack2[-1]]:
t=stack2.pop()
delete_order2.append(t)
stack2.append(i)
for i in stack2[::-1]:
delete_order2.append(i)
delete_order1=delete_order1[::-1]
delete_order2=delete_order2[::-1]
generate1=[]
generate2=[]
cur=''
lst1=[]
lst2=[]
# 将 nums1 的所有可能的子序列的非降序排列按顺序添加到 generate1
for i in delete_order1:
t=bisect_left(lst1,i)
lst1[t:t]=[i]
cur=cur[:t]+str(nums1[i])+cur[t:]
generate1.append(cur)
cur=''
# 将 nums2 的所有可能的子序列的非降序排列按顺序添加到 generate2
for i in delete_order2:
t=bisect_left(lst2,i)
lst2[t:t]=[i]
cur=cur[:t]+str(nums2[i])+cur[t:]
generate2.append(cur)
ans=[]
# 合并两个序列成最大的数
def join_max(s1,s2):
i=0
j=0
ans=''
while i<len(s1) or j<len(s2):
if i==len(s1):
ans+=s2[j:]
return ans
if j==len(s2):
ans+=s1[i:]
return ans
if (s1[i:])<=(s2[j:]):
ans+=s2[j]
j+=1
else:
ans+=s1[i]
i+=1
return ans
cmax=0
for i in range(max(0,k-n),min(m,k)+1):
if i==0 :
cmax=max(cmax,int(generate2[k-1]))
elif i==k:
cmax=max(cmax,int(generate1[k-1]))
else:
s1=generate1[i-1]
s2=generate2[k-i-1]
tmp=join_max(s1,s2)
cmax=max(cmax,int(tmp))
return list(map(int,list(str(cmax))))
单调栈是一种特殊的栈结构，用于在遍历数组时维护一个单调递增或单调递减的序列。在拼接最大数的问题中，我们使用单调递减栈。这是因为我们希望尽可能地让高位的数字大，以此来构造一个最大的数。单调栈可以帮助我们处理当前数字和栈顶数字的关系，如果当前数字比栈顶数字大，则将栈顶数字弹出，这样可以确保在不违反选取数字个数限制的前提下，尽可能地让后续的大数字处于高位，从而构成更大的数。单调栈确保了每次插入操作后栈内元素的单调性，这样生成的序列自然是最大的非降序排列。
在合并两个子序列时，如果遇到`s1[i:] == s2[j:]`的情况，即从当前位置开始两个子序列的剩余部分完全相等，我们可以选择任意一个序列中的下一个数字，因为它们会给出相同的结果。然而，为了避免在实现中出现不必要的复杂性，通常的做法是按照一定的顺序（例如先取`s1`或先取`s2`）来推进，这可以简化代码逻辑。实际操作中，我们可以基于其他条件（如先到达序列末尾的情况）来调整选择策略，以确保合并后的序列尽可能大。
在从数组中构造子序列时，我们需要确保取出的数字保持其在原数组中的相对顺序。这可以通过遍历数组的同时使用单调栈来实现。单调栈操作只涉及栈顶元素的比较和可能的弹出，这不会影响未处理的元素的顺序。因此，已经进入栈中的元素（即已经被选择加入到子序列中的元素）的相对顺序是保持不变的。这样，即使在进行删除操作（弹栈操作）时，也只是选择不将某些元素加入子序列，而不会改变已加入元素的顺序。