321. 拼接最大数

321. 拼接最大数 #

leetcode 链接： https://leetcode-cn.com/problems/create-maximum-number/

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明：请尽可能地优化你算法的时间和空间复杂度。

示例 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]

方法一：单调栈

为了求得长度为 k 的最大子序列，需要从两个数组中分别选出最大的子序列，然后将这两个子序列合并得到最大数。两个子序列的长度最小为 0，最大不能超过 k 且不能超过对应的数组长度。所以整个算法就分成三步：

  1. 分别计算 num1 和 nums2 的最大子序列
  2. 按照字典序降序合并子序列
  3. 保存对应的整数较大的子序列
func maxNumber(nums1 []int, nums2 []int, k int) []int {
	initialSize := 0
	if len(nums2) < k {
		initialSize = k - len(nums2)
	}
	var ans []int
	for size := initialSize; size <= k && size <= len(nums1); size++ {
		sub1 := maxSubSequence(nums1, size)
		sub2 := maxSubSequence(nums2, k-size)
		merged := merge(sub1, sub2)
		if lexicographicalLess(ans, merged) {
			ans = merged
		}
	}
	return ans
}

// 按照字典序降序合并
func merge(sub1, sub2 []int) []int {
	var merged = make([]int, len(sub1)+len(sub2))
	for i := range merged {
		if lexicographicalLess(sub1, sub2) {
			merged[i], sub2 = sub2[0], sub2[1:]
		} else {
			merged[i], sub1 = sub1[0], sub1[1:]
		}
	}
	return merged
}

// 判断字典序大小
func lexicographicalLess(sub1, sub2 []int) bool {
	for i := 0; i < len(sub1) && i < len(sub2); i++ {
		if sub1[i] != sub2[i] {
			return sub1[i] < sub2[i]
		}
	}
	return len(sub1) < len(sub2)
}

// 单调栈求指定长度的最大子序列
func maxSubSequence(nums []int, k int) []int {
	var sub []int
	for i := range nums {
		for len(sub) > 0 && nums[i] > sub[len(sub)-1] && len(sub)+len(nums)-i-1 >= k {
			sub = sub[:len(sub)-1]
		}
		if len(sub) < k {
			sub = append(sub, nums[i])
		}
	}
	return sub
}
Calendar March 3, 2024