LeetCode 题解工作台
拼接最大数
给你两个整数数组 nums1 和 nums2 ，它们的长度分别为 m 和 n 。数组 nums1 和 nums2 分别代表两个数各位上的数字。同时你也会得到一个整数 k 。 请你利用这两个数组中的数字创建一个长度为 k 的最大数。同一数组中数字的相对顺序必须保持不变。 返回代表答案的长度为 k 的数…
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 双·指针·invariant
答案摘要
我们可以枚举从数组 中取出 个数，那么从数组 中就需要取出 个数。其中 $x \in [max(0, k-n), min(k, m)]$。 对于每一个 ，我们可以使用单调栈求出数组 中长度为 的最大子序列，以及数组 中长度为 的最大子序列。然后将这两个子序列合并得到长度为 的最大子序列。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你两个整数数组 nums1 和 nums2，它们的长度分别为 m 和 n。数组 nums1 和 nums2 分别代表两个数各位上的数字。同时你也会得到一个整数 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]
提示：
m == nums1.lengthn == nums2.length1 <= m, n <= 5000 <= nums1[i], nums2[i] <= 91 <= k <= m + nnums1和nums2没有前导 0。
解题思路
方法一：枚举 + 单调栈
我们可以枚举从数组 中取出 个数，那么从数组 中就需要取出 个数。其中 。
对于每一个 ，我们可以使用单调栈求出数组 中长度为 的最大子序列，以及数组 中长度为 的最大子序列。然后将这两个子序列合并得到长度为 的最大子序列。
最后，我们比较所有的长度为 的最大子序列，找出最大的序列即可。
时间复杂度 ，空间复杂度 。其中 和 分别是数组 和 的长度。
class Solution:
def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
def f(nums: List[int], k: int) -> List[int]:
n = len(nums)
stk = [0] * k
top = -1
remain = n - k
for x in nums:
while top >= 0 and stk[top] < x and remain > 0:
top -= 1
remain -= 1
if top + 1 < k:
top += 1
stk[top] = x
else:
remain -= 1
return stk
def compare(nums1: List[int], nums2: List[int], i: int, j: int) -> bool:
if i >= len(nums1):
return False
if j >= len(nums2):
return True
if nums1[i] > nums2[j]:
return True
if nums1[i] < nums2[j]:
return False
return compare(nums1, nums2, i + 1, j + 1)
def merge(nums1: List[int], nums2: List[int]) -> List[int]:
m, n = len(nums1), len(nums2)
i = j = 0
ans = [0] * (m + n)
for k in range(m + n):
if compare(nums1, nums2, i, j):
ans[k] = nums1[i]
i += 1
else:
ans[k] = nums2[j]
j += 1
return ans
m, n = len(nums1), len(nums2)
l, r = max(0, k - n), min(k, m)
ans = [0] * k
for x in range(l, r + 1):
arr1 = f(nums1, x)
arr2 = f(nums2, k - x)
arr = merge(arr1, arr2)
if ans < arr:
ans = arr
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates understanding of two-pointer scanning and invariant tracking.
- question_mark
The candidate can articulate why a greedy approach works in this problem and how monotonic stacks are used.
- question_mark
The candidate shows ability to merge results from multiple arrays while maintaining order and maximizing the result.
常见陷阱
外企场景- error
Failing to maintain the relative order of digits from each array.
- error
Choosing digits greedily without considering the impact on future selections.
- error
Incorrectly merging the two arrays and not adjusting the pointer positions properly.
进阶变体
外企场景- arrow_right_alt
Problem with larger arrays where the number k is near the total length of nums1 and nums2.
- arrow_right_alt
A version where only one array is non-empty.
- arrow_right_alt
A variation where the target number length k is smaller than the combined length of nums1 and nums2.