Leetcode 321. Create Maximum Number
程序员文章站
2022-04-25 14:42:08
...
这道题的步骤如下:
1.将k拆分成两个数i,k-i,分别表示从nums1,nums2中取出的数个数
2.从nums1, nums2中取出相应个数的最大的数
3.将这两个最大的数merge成一个数
4.遍历所有的k拆分情况,得到最终Maximum Number
对于步骤2,如何从一个数组中取出给定个数(记作M)的最大数,需要用递减栈的思想:
初始化stack, 遍历数组中的数nums[i]:
如果stack为空或者nums[i]小于stack最后一个元素,则直接将nums[i]压入栈
否则将stack末尾元素pop(直到剩余数组不足以填充大小为M的栈,或者stack末尾元素≥nums[i]),并将nums[i]压入栈。
最后得到的stack前M为即位最大数。
对于步骤3,如何用两个数组merge成一个最大数,用的是归并排序中的merge的思想:
初始化nums数组,维护nums1和nums2的当前元素指针i,j
如果nums1[i] > nums2[j],则将nums1[i]放入nums中,并且i++
如果nums1[i] < nums2[j],则将nums2[j]放入nums中,并且j++
如果nums1[i] == nums2[j],比较nums1[i+1:]与nums2[j+1:]大小,将较大的一方前面的数放入nums中,并更新指针。
class Solution(object):
def maxNumberK(self, nums, k):
stack = []
for i, num in enumerate(nums):
if not stack or num <= stack[-1]:
stack.append(num)
continue
else:
while stack and len(stack) - 1 + len(nums) - i >= k and stack[-1] < num:
del stack[-1]
stack.append(num)
return stack[:k]
def merge(self, nums1, nums2):
nums = []
point1, point2 = 0, 0
while len(nums) < len(nums1) + len(nums2):
if point1 >= len(nums1):
nums.extend(nums2[point2:])
elif point2 >= len(nums2):
nums.extend(nums1[point1:])
else:
if nums1[point1] > nums2[point2]:
nums.append(nums1[point1])
point1 += 1
elif nums2[point2] > nums1[point1]:
nums.append(nums2[point2])
point2 += 1
else:
if nums1[point1 + 1:] >= nums2[point2 + 1:]:
nums.append(nums1[point1])
point1 += 1
else:
nums.append(nums2[point2])
point2 += 1
return nums
def maxNumber(self, nums1, nums2, k):
"""
:type nums1: List[int]
:type nums2: List[int]
:type k: int
:rtype: List[int]
"""
result = []
for i in range(k+1):
# nums1中有i个数
# nums2中有k-i个数
if i > len(nums1) or k-i > len(nums2):
continue
nums1_k = self.maxNumberK(nums1, i)
nums2_k = self.maxNumberK(nums2, k-i)
nums = self.merge(nums1_k, nums2_k)
result = max(result, nums)
return result
推荐阅读
-
Leetcode 1456. Maximum Number of Vowels in a Substring of Given Length (python)
-
【Leetcode】1072. Flip Columns For Maximum Number of Equal Rows(异或运算)
-
321. Create Maximum Number
-
#leetcode#321.Create Maximum Number
-
Leetcode 321. Create Maximum Number
-
【Leetcode】414.Third Maximum Number
-
[LeetCode]414. Third Maximum Number
-
Leetcode 414. Third Maximum Number