LeetCode 题解工作台
构造最长非递减子数组
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度均为 n 。 让我们定义另一个下标从 0 开始、长度为 n 的整数数组， nums3 。对于范围 [0, n - 1] 的每个下标 i ，你可以将 nums1[i] 或 nums2[i] 的值赋给 nums3[i] 。 你的任务是…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义两个变量 和 ，分别表示当前位置的最长非递减子数组长度，其中 表示以 元素为结尾的最长非递减子数组长度，而 表示以 元素为结尾的最长非递减子数组长度。初始时 $f = g = 1$，初始答案 $ans = 1$。 接下来，我们在 $i \in [1, n)$ 的范围内遍历数组元素，对于每个 ，我们定义两个变量 和 ，分别表示以 和 元素为结尾的最长非递减子数组长度，初始化时…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度均为 n 。
让我们定义另一个下标从 0 开始、长度为 n 的整数数组，nums3 。对于范围 [0, n - 1] 的每个下标 i ，你可以将 nums1[i] 或 nums2[i] 的值赋给 nums3[i] 。
你的任务是使用最优策略为 nums3 赋值，以最大化 nums3 中 最长非递减子数组 的长度。
以整数形式表示并返回 nums3 中 最长非递减 子数组的长度。
注意：子数组 是数组中的一个连续非空元素序列。
示例 1：
输入：nums1 = [2,3,1], nums2 = [1,2,1] 输出：2 解释：构造 nums3 的方法之一是： nums3 = [nums1[0], nums2[1], nums2[2]] => [2,2,1] 从下标 0 开始到下标 1 结束，形成了一个长度为 2 的非递减子数组 [2,2] 。 可以证明 2 是可达到的最大长度。
示例 2：
输入：nums1 = [1,3,2,1], nums2 = [2,2,3,4] 输出：4 解释：构造 nums3 的方法之一是： nums3 = [nums1[0], nums2[1], nums2[2], nums2[3]] => [1,2,3,4] 整个数组形成了一个长度为 4 的非递减子数组，并且是可达到的最大长度。
示例 3：
输入：nums1 = [1,1], nums2 = [2,2] 输出：2 解释：构造 nums3 的方法之一是： nums3 = [nums1[0], nums1[1]] => [1,1] 整个数组形成了一个长度为 2 的非递减子数组，并且是可达到的最大长度。
提示：
1 <= nums1.length == nums2.length == n <= 1051 <= nums1[i], nums2[i] <= 109
解题思路
方法一：动态规划
我们定义两个变量 和 ，分别表示当前位置的最长非递减子数组长度，其中 表示以 元素为结尾的最长非递减子数组长度，而 表示以 元素为结尾的最长非递减子数组长度。初始时 ，初始答案 。
接下来，我们在 的范围内遍历数组元素，对于每个 ，我们定义两个变量 和 ，分别表示以 和 元素为结尾的最长非递减子数组长度，初始化时 。
我们可以通过 和 的值来计算出 和 的值：
- 如果 ，那么 ；
- 如果 ，那么 ；
- 如果 ，那么 ；
- 如果 ，那么 。
然后，我们更新 和 ，并将 更新为 。
遍历结束后，我们返回 即可。
时间复杂度 ，其中 是数组的长度。空间复杂度 。
class Solution:
def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
f = g = 1
ans = 1
for i in range(1, n):
ff = gg = 1
if nums1[i] >= nums1[i - 1]:
ff = max(ff, f + 1)
if nums1[i] >= nums2[i - 1]:
ff = max(ff, g + 1)
if nums2[i] >= nums1[i - 1]:
gg = max(gg, f + 1)
if nums2[i] >= nums2[i - 1]:
gg = max(gg, g + 1)
f, g = ff, gg
ans = max(ans, f, g)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each index is processed once and updates two states. Space complexity is O(n) for dp1 and dp2, or O(1) if using rolling variables instead of full arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may hint at using DP and tracking two choices per index.
- question_mark
Expect questions about handling equal values or non-decreasing conditions.
- question_mark
They might ask about optimizing space from O(n) to O(1) using rolling variables.
常见陷阱
外企场景- error
Forgetting to consider both previous dp1 and dp2 values when updating the current state.
- error
Misinterpreting non-decreasing as strictly increasing.
- error
Not initializing the first element correctly, leading to off-by-one errors.
进阶变体
外企场景- arrow_right_alt
Find the longest non-decreasing subarray when more than two arrays are available to choose from.
- arrow_right_alt
Determine the maximum sum of the non-decreasing subarray instead of the length.
- arrow_right_alt
Compute the number of distinct longest non-decreasing subarrays constructible from two arrays.