题目描述
给你两个下标从 0 开始的整数数组 nums1
和 nums2
,长度均为 n
。
让我们定义另一个下标从 0 开始、长度为 n
的整数数组,nums3
。对于范围 [0, n - 1]
的每个下标 i
,你可以将 nums1[i]
或 nums2[i]
的值赋给 nums3[i]
。
你的任务是使用最优策略为 nums3
赋值,以最大化 nums3
中 最长非递减子数组 的长度。
以整数形式表示并返回 nums3
中 最长非递减 子数组的长度。
注意:子数组 是数组中的一个连续非空元素序列。
样例
输入: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 是可达到的最大长度。
输入: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 的非递减子数组,并且是可达到的最大长度。
输入:nums1 = [1,1], nums2 = [2,2]
输出:2
解释:构造 nums3 的方法之一是:
nums3 = [nums1[0], nums1[1]] => [1,1]
整个数组形成了一个长度为 2 的非递减子数组,并且是可达到的最大长度。
限制
1 <= nums1.length == nums2.length == n <= 10^5
1 <= nums1[i], nums2[i] <= 10^9
算法
(动态规划) $O(n)$
- 设状态 $f(i)$ 表示遍历到下标 $i$ 且 $nums3(i)$ 为 $nums1(i)$ 时的最长非递减子数组,$g(i)$ 表示遍历到下标 $i$ 且 $nums3(i)$ 为 $nums2(i)$ 时的最长非递减子数组。
- 初始时,$f(0) = g(0) = 1$,其余为 $1$ 待定。
- 转移时,对于 $f(i)$,如果 $nums1(i) \ge nums1(i - 1)$,则转移 $f(i) = \max(f(i), f(i - 1) + 1)$;如果 $nums1(i) \ge nums2(i - 1)$,则转移 $f(i) = \max(f(i), g(i - 1) + 1)$;对于 $g(i)$ 转移同理。
- 最终答案为 $\max(f(i), g(i))$。
- 由于每个状态只依赖前一位的状态,所以可以优化状态表示为两个变量。
时间复杂度
- 状态数为 $O(n)$,转移时间为常数,故时间复杂度为 $O(n)$。
空间复杂度
- 优化状态表示后,仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
const int n = nums1.size();
int f = 1, g = 1, ans = 1;
for (int i = 1; i < n; i++) {
int nf = 1, ng = 1;
if (nums1[i] >= nums1[i - 1])
nf = max(nf, f + 1);
if (nums1[i] >= nums2[i - 1])
nf = max(nf, g + 1);
if (nums2[i] >= nums1[i - 1])
ng = max(ng, f + 1);
if (nums2[i] >= nums2[i - 1])
ng = max(ng, g + 1);
f = nf; g = ng;
ans = max(ans, max(f, g));
}
return ans;
}
};