欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 321. Create Maximum Number

程序员文章站 2022-04-25 14:42:08
...

Leetcode 321. Create Maximum Number

这道题的步骤如下:

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
            
            
            

 

 

 

相关标签: 算法