321. 拼接最大数
class Solution(object):
def maxNumber(self, nums1, nums2, k):
m, n = len(nums1), len(nums2)
maxSubsequence = [0] * k
start, 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 = curMaxSubsequence
return maxSubsequence
def getMaxSubsequence(self,nums,k):
if k == 0:
return []
stack = [0]*k
stack[0] = nums[0]
i = 1
for j in range(1,len(nums)):
if len(nums)-j > k-i:
if nums[j] <= stack[i-1] and i < k:
stack[i] = nums[j]
i += 1
elif nums[j] > stack[i-1]:
while i >= 1 and nums[j] > stack[i-1] and len(nums)-j > k-i:
stack[i-1] = nums[j]
i -= 1
i += 1
else:
stack[i] = nums[j]
i += 1
return stack
def merge(self, subsequence1, subsequence2):
x, y = len(subsequence1), len(subsequence2)
if x == 0:
return subsequence2
if y == 0:
return subsequence1
mergeLength = x + y
merged = list()
index1 = index2 = 0
for _ in range(mergeLength):
if self.compare(subsequence1, index1, subsequence2, index2) > 0:
merged.append(subsequence1[index1])
index1 += 1
else:
merged.append(subsequence2[index2])
index2 += 1
return merged
def compare(self, subsequence1, index1, subsequence2, index2):
x, y = len(subsequence1), len(subsequence2)
while index1 < x and index2 < y:
difference = subsequence1[index1] - subsequence2[index2]
if difference != 0:
return difference
index1 += 1
index2 += 1
return (x - index1) - (y - index2)
单调栈
def getMaxSubsequence(self,nums,k):
if k == 0:
return []
stack = [0]*k
stack[0] = nums[0]
i = 1
for j in range(1,len(nums)):
if len(nums)-j > k-i:
if nums[j] <= stack[i-1] and i < k:
stack[i] = nums[j]
i += 1
elif nums[j] > stack[i-1]:
while i >= 1 and nums[j] > stack[i-1] and len(nums)-j > k-i:
stack[i-1] = nums[j]
i -= 1
i += 1
else:
stack[i] = nums[j]
i += 1
return stack
这一部分的目的是按顺序找到nums数列中能组成最大数的k个元素。
我这里的逻辑是，如果k=0那就直接出空数组，不然肯定至少有一位，就先直接把第一位填进去，然后遍历nums数组进行更新。
当nums剩下的位数比stack剩下的位数更多时，意思就是我们还可以在剩下的nums里挑选最大的，这种情况下，我们也可以继续更新stack的上一位：
- 当nums[j] 比 stack的上一位更小时，stack上一位可以保持，i继续往后所以加一位；
- 当nums[j] 比 stack的上一位更大时，我们就需要更新上一位，而且要继续往上更新，所以这里用的应该是while而不是if，进入while之后我们也需要保证nums剩下的位数比stack剩下的位数更多，不然最后会导致填不满stack，以及i是在索引范围内的。
- 出了while之后，因为stack现在所在的那一位被填上了，所以i也需要往后一位。
一直遍历到当nums剩下的位数比stack剩下的位数相同时，意思就是我们可以不用再比较大小了，后面所有的都可以一起填进去了，再作比较就会导致位数不满。
nums = [8,7,3,6,8] k = 2
stack = [0,0]
stack = [8,0] i =1 j = 1
stack = [8,7] i =2 j = 2
stack = [8,7] i =2 j = 3, 3不更新
stack = [8,7] i =2 j = 4, 6不更新
stack = [8,8] i =2 j = 4, 8更新
比较大小
def compare(self, subsequence1, index1, subsequence2, index2):
x, y = len(subsequence1), len(subsequence2)
while index1 < x and index2 < y:
difference = subsequence1[index1] - subsequence2[index2]
if difference != 0:
return difference
index1 += 1
index2 += 1
return (x - index1) - (y - index2)
进while循环，在不出范围的情况下，比较当前位置的大小，如果不一样的话，就可以直接出去了，如果一样就比较下一位，如果一直到其中一个数列走完索引了，还是一样的，就看另一位是否还有剩余。
合并为最大数
def merge(self, subsequence1, subsequence2):
x, y = len(subsequence1), len(subsequence2)
if x == 0:
return subsequence2
if y == 0:
return subsequence1
mergeLength = x + y
merged = list()
index1 = index2 = 0
for _ in range(mergeLength):
if self.compare(subsequence1, index1, subsequence2, index2) > 0:
merged.append(subsequence1[index1])
index1 += 1
else:
merged.append(subsequence2[index2])
index2 += 1
return merged
这里的逻辑很简单就是 nums1现在的位置更大就先出nums1，nums2 现在的位置更大就先出nums2，一样的情况在比较大小那里已经解决了。
主代码
class Solution(object):
def maxNumber(self, nums1, nums2, k):
m, n = len(nums1), len(nums2)
maxSubsequence = [0] * k
start, 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 = curMaxSubsequence
return maxSubsequence
首先最后一次比较大小，大家的位数肯定是一样的，都是k位，那就可以一位一位的比较了，所以用上面那个比较大小的函数就可以。