日常刷题(24)
1. 拼接最大数
1.1. 题目描述
给你两个整数数组 nums1 和 nums2，它们的长度分别为 m 和 n。数组 nums1 和 nums2 分别代表两个数各位上的数字。同时你也会得到一个整数 k。
请你利用这两个数组中的数字中创建一个长度为 k <= m + n 的最大数，在这个必须保留来自同一数组的数字的相对顺序。
返回代表答案的长度为 k 的数组。
1.2. 示例
示例 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]
1.3. 题目解析
- 找最大子串
- 拼接最大子串
1.4. 代码
class Solution:
def get_max_subsequence(self, nums, k):
stack = []
drop = len(nums) - k
for num in nums:
while stack and drop and stack[-1] < num:
stack.pop()
drop -= 1
stack.append(num)
return stack
def merge(self, nums1, nums2):
stack = []
while nums1 or nums2:
# 比较第一位数大小
nums = nums1 if nums1 > nums2 else nums2
stack.append(nums.pop(0))
return stack
def __call__(self, nums1, nums2, k):
ans = []
for i in range(k):
if i > len(nums1) or k - i > len(nums2):
continue
stack1, stack2 = self.get_max_subsequence(nums1, i), self.get_max_subsequence(nums2, k - i)
stack = self.merge(stack1, stack2)[:k]
if len(stack) != k:
continue
ans = max(stack, ans)
return ans