构造最长非递减子数组
难度:
标签:
题目描述
You are given two 0-indexed integer arrays nums1 and nums2 of length n.
Let's define another 0-indexed integer array, nums3, of length n. For each index i in the range [0, n - 1], you can assign either nums1[i] or nums2[i] to nums3[i].
Your task is to maximize the length of the longest non-decreasing subarray in nums3 by choosing its values optimally.
Return an integer representing the length of the longest non-decreasing subarray in nums3.
Note: A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums1 = [2,3,1], nums2 = [1,2,1] Output: 2 Explanation: One way to construct nums3 is: nums3 = [nums1[0], nums2[1], nums2[2]] => [2,2,1]. The subarray starting from index 0 and ending at index 1, [2,2], forms a non-decreasing subarray of length 2. We can show that 2 is the maximum achievable length.
Example 2:
Input: nums1 = [1,3,2,1], nums2 = [2,2,3,4] Output: 4 Explanation: One way to construct nums3 is: nums3 = [nums1[0], nums2[1], nums2[2], nums2[3]] => [1,2,3,4]. The entire array forms a non-decreasing subarray of length 4, making it the maximum achievable length.
Example 3:
Input: nums1 = [1,1], nums2 = [2,2] Output: 2 Explanation: One way to construct nums3 is: nums3 = [nums1[0], nums1[1]] => [1,1]. The entire array forms a non-decreasing subarray of length 2, making it the maximum achievable length.
Constraints:
1 <= nums1.length == nums2.length == n <= 1051 <= nums1[i], nums2[i] <= 109
代码结果
运行时间: 122 ms, 内存: 31.3 MB
/*
* 思路：
* 我们需要构建一个新的数组 nums3，使其形成最长的非递减子数组。
* 对于每个下标 i，我们可以选择 nums1[i] 或 nums2[i]。
* 我们可以使用动态规划的方法来解决这个问题。
* 我们用两个数组 dp1 和 dp2 来分别记录当选择 nums1[i] 和 nums2[i] 时，
* 当前最长的非递减子数组的长度。
* 最终答案是 dp1 和 dp2 中的最大值。
* 使用 Java Stream 来简化数组的初始化和计算过程。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxNonDecreasingLength(int[] nums1, int[] nums2) {
int n = nums1.length;
int[] dp1 = new int[n];
int[] dp2 = new int[n];
dp1[0] = 1;
dp2[0] = 1;
int[] maxLen = {1};
IntStream.range(1, n).forEach(i -> {
dp1[i] = nums1[i] >= nums1[i - 1] ? dp1[i - 1] + 1 : 1;
dp2[i] = nums2[i] >= nums2[i - 1] ? dp2[i - 1] + 1 : 1;
if (nums1[i] >= nums2[i - 1]) dp1[i] = Math.max(dp1[i], dp2[i - 1] + 1);
if (nums2[i] >= nums1[i - 1]) dp2[i] = Math.max(dp2[i], dp1[i - 1] + 1);
maxLen[0] = Math.max(maxLen[0], Math.max(dp1[i], dp2[i]));
});
return maxLen[0];
}
}
解释
方法:
题解的核心思路是为 nums3 构造一个尽可能长的非递减子数组。首先，对于每个索引 i，如果 nums1[i] 小于 nums2[i]，则交换这两个值以使 nums2[i] 总是较小的一个，这有助于维持 nums3 的非递减特性。对于每个元素，尝试将其添加到 nums3 中，如果添加后导致数组非递减顺序被破坏，则尝试回溯到之前的点，并从那里重新开始尝试构建非递减子数组。通过这种方式，算法试图找到尽可能长的非递减序列。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中提到，如果 nums1[i] 小于 nums2[i] 就会交换这两个值，这种策略是基于什么考虑？是否总是有助于构建最长的非递减子数组？
▷🦆
题解中提到了回溯的策略，能否详细解释何时触发回溯以及回溯的具体操作？
▷🦆
当 nums2[i] 小于 nums3 的最后一个元素时，题解选择设置一个回溯点并可能回溯，这种方法为何能有效地增加非递减子数组的长度？
▷🦆
题解中提到如果两个选项（nums1[i] 和 nums2[i]）都无法添加到 nums3 中时会发生回溯，这种情况具体是如何处理的？
▷