构造最长非递减子数组

难度: Medium

给你两个下标从 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 <= 10⁵
1 <= nums1[i], nums2[i] <= 10⁹

Submission

运行时间: 122 ms

内存: 31.3 MB

class Solution:
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
        nums3 = []
        max_length = 0
        i = j = 0
        locked = False
        while i < len(nums1):
            if nums1[i] < nums2[i]:
                nums1[i], nums2[i] = nums2[i], nums1[i]

            if not nums3:
                nums3.append(nums2[i])
            else:
                if nums2[i] < nums3[-1]:
                    if not locked:
                        j = i
                        locked = True
                    if nums1[i] < nums3[-1]:
                        i = j
                        locked = False
                        max_length = max(max_length, len(nums3))
                        nums3 = [nums2[i]]
                    else:
                        nums3.append(nums1[i])
                else:
                    nums3.append(nums2[i])

            i += 1

        return max(max_length, len(nums3))

Explain

题解的核心思路是为 nums3 构造一个尽可能长的非递减子数组。首先，对于每个索引 i，如果 nums1[i] 小于 nums2[i]，则交换这两个值以使 nums2[i] 总是较小的一个，这有助于维持 nums3 的非递减特性。对于每个元素，尝试将其添加到 nums3 中，如果添加后导致数组非递减顺序被破坏，则尝试回溯到之前的点，并从那里重新开始尝试构建非递减子数组。通过这种方式，算法试图找到尽可能长的非递减序列。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
        nums3 = []  # 用于构建最终的非递减数组
        max_length = 0  # 记录最长非递减子数组的长度
        i = j = 0  # i 是当前索引，j 是回溯点的索引
        locked = False  # 是否锁定回溯点
        while i < len(nums1):
            if nums1[i] < nums2[i]:  # 确保 nums2[i] 是较小的值
                nums1[i], nums2[i] = nums2[i], nums1[i]

            if not nums3:  # 如果 nums3 为空，直接添加
                nums3.append(nums2[i])
            else:
                if nums2[i] < nums3[-1]:  # 如果当前元素小于 nums3 的最后一个元素
                    if not locked:  # 如果还未设置回溯点
                        j = i
                        locked = True
                    if nums1[i] < nums3[-1]:  # 如果两个选项都无法添加
                        i = j  # 回溯到 j 点
                        locked = False  # 重置锁定状态
                        max_length = max(max_length, len(nums3))  # 更新最大长度
                        nums3 = [nums2[i]]  # 重新开始构建 nums3
                    else:
                        nums3.append(nums1[i])  # 添加 nums1[i]
                else:
                    nums3.append(nums2[i])  # 直接添加 nums2[i]

            i += 1  # 移动到下一个索引

        return max(max_length, len(nums3))  # 返回最大长度

Explore

这种策略的基本考虑是确保 nums2[i] 是较小的值，这有助于维持或扩展非递减子数组 nums3。通过让 nums2[i] 始终是较小的，我们可以优先考虑将这个较小的值添加到子数组中，从而增加成功添加而不破坏非递减顺序的可能性。虽然这种方法在很多情况下有助于构建较长的非递减子数组，但并不能保证总是如此，因为最优的选择可能取决于后续元素的值。

回溯被触发当添加当前元素 nums2[i] 到子数组 nums3 会破坏非递减顺序时。在这种情况下，如果还未设置回溯点 j，就会设置当前索引 i 为回溯点 j，并锁定回溯点。如果在后续的尝试中发现 nums1[i] 和 nums2[i] 均不能被添加而不破坏顺序，算法会回溯到 j 点，重置当前的 nums3 为从 nums2[j] 开始重新尝试构建，并取消锁定状态，以便在必要时重新设置新的回溯点。这样的回溯策略有助于撤销之前可能导致长度不最大化的决策。

当 nums2[i] 小于 nums3 的最后一个元素时，意味着直接添加 nums2[i] 会破坏数组的非递减性。设置回溯点并在必要时回溯，允许算法有机会撤销之前的添加操作，从而尝试不同的元素组合以找到可能更长的非递减子数组。这种方法增加了灵活性和尝试不同路径的能力，有助于找到一个尽可能长的非递减序列。

当 nums1[i] 和 nums2[i] 都无法添加到 nums3 而不破坏非递减顺序时，算法执行回溯操作。具体地，算法会回到先前设置的回溯点 j，并从该点重新尝试构建非递减子数组，同时重置 nums3 和锁定状态。这种操作有助于撤销可能导致非最优长度的添加决策，从而增加获得更长非递减子数组的可能性。