题目:
题解:
class Solution:def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:m, n = len(nums1), len(nums2)maxSubsequence = [0] * kstart, end = max(0, k - n), min(k, m)for i in range(start, end + 1):subsequence1 = self.getMaxSubsequence(nums1, i)subsequence2 = self.getMaxSubsequence(nums2, k - i)curMaxSubsequence = self.merge(subsequence1, subsequence2)if self.compare(curMaxSubsequence, 0, maxSubsequence, 0) > 0:maxSubsequence = curMaxSubsequencereturn maxSubsequencedef getMaxSubsequence(self, nums: List[int], k: int) -> int:stack = [0] * ktop = -1remain = len(nums) - kfor i, num in enumerate(nums):while top >= 0 and stack[top] < num and remain > 0:top -= 1remain -= 1if top < k - 1:top += 1stack[top] = numelse:remain -= 1return stackdef merge(self, subsequence1: List[int], subsequence2: List[int]) -> List[int]:x, y = len(subsequence1), len(subsequence2)if x == 0:return subsequence2if y == 0:return subsequence1mergeLength = x + ymerged = list()index1 = index2 = 0for _ in range(mergeLength):if self.compare(subsequence1, index1, subsequence2, index2) > 0:merged.append(subsequence1[index1])index1 += 1else:merged.append(subsequence2[index2])index2 += 1return mergeddef compare(self, subsequence1: List[int], index1: int, subsequence2: List[int], index2: int) -> int:x, y = len(subsequence1), len(subsequence2)while index1 < x and index2 < y:difference = subsequence1[index1] - subsequence2[index2]if difference != 0:return differenceindex1 += 1index2 += 1return (x - index1) - (y - index2)