Medium

题目描述

给你两个长度为 n 的 0 索引整数数组 nums1 和 nums2。

我们定义另一个长度为 n 的 0 索引整数数组 nums3。对于范围 [0, n - 1] 内的每个索引 i，你可以将 nums1[i] 或 nums2[i] 赋值给 nums3[i]。

你的任务是通过最优选择 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^5
  • 1 <= nums1[i], nums2[i] <= 10^9

解题思路

这是一道典型的动态规划问题。我们需要在每个位置选择来自 nums1 或 nums2 的值，使得构成的数组中最长非递减子数组尽可能长。

解题思路

状态定义：

  • dp[i][0]：以 nums1[i] 结尾的最长非递减子数组长度
  • dp[i][1]：以 nums2[i] 结尾的最长非递减子数组长度

状态转移： 对于位置 i，我们考虑选择 nums1[i] 或 nums2[i]：

  1. 选择 nums1[i] 时：

    • 如果 nums1[i] >= nums1[i-1]，则 dp[i][0] = max(dp[i][0], dp[i-1][0] + 1)
    • 如果 nums1[i] >= nums2[i-1]，则 dp[i][0] = max(dp[i][0], dp[i-1][1] + 1)

  2. 选择 nums2[i] 时：

    • 如果 nums2[i] >= nums1[i-1]，则 dp[i][1] = max(dp[i][1], dp[i-1][0] + 1)
    • 如果 nums2[i] >= nums2[i-1]，则 dp[i][1] = max(dp[i][1], dp[i-1][1] + 1)

初始化： dp[0][0] = dp[0][1] = 1，因为单个元素构成长度为1的非递减子数组。

空间优化： 由于每次状态转移只依赖前一个位置的状态，可以使用滚动数组将空间复杂度优化到 O(1)。

代码实现

class Solution {
public:
    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int dp0 = 1, dp1 = 1;  // dp[i][0] and dp[i][1]
        int result = 1;
        
        for (int i = 1; i < n; i++) {
            int newDp0 = 1, newDp1 = 1;
            
            // Choose nums1[i]
            if (nums1[i] >= nums1[i-1]) {
                newDp0 = max(newDp0, dp0 + 1);
            }
            if (nums1[i] >= nums2[i-1]) {
                newDp0 = max(newDp0, dp1 + 1);
            }
            
            // Choose nums2[i]
            if (nums2[i] >= nums1[i-1]) {
                newDp1 = max(newDp1, dp0 + 1);
            }
            if (nums2[i] >= nums2[i-1]) {
                newDp1 = max(newDp1, dp1 + 1);
            }
            
            dp0 = newDp0;
            dp1 = newDp1;
            result = max(result, max(dp0, dp1));
        }
        
        return result;
    }
};

class Solution:
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        dp0, dp1 = 1, 1  # dp[i][0] and dp[i][1]
        result = 1
        
        for i in range(1, n):
            new_dp0, new_dp1 = 1, 1
            
            # Choose nums1[i]
            if nums1[i] >= nums1[i-1]:
                new_dp0 = max(new_dp0, dp0 + 1)
            if nums1[i] >= nums2[i-1]:
                new_dp0 = max(new_dp0, dp1 + 1)
            
            # Choose nums2[i]
            if nums2[i] >= nums1[i-1]:
                new_dp1 = max(new_dp1, dp0 + 1)
            if nums2[i] >= nums2[i-1]:
                new_dp1 = max(new_dp1, dp1 + 1)
            
            dp0, dp1 = new_dp0, new_dp1
            result = max(result, dp0, dp1)
        
        return result

public class Solution {
    public int MaxNonDecreasingLength(int[] nums1, int[] nums2) {
        int n = nums1.Length;
        int dp0 = 1, dp1 = 1;  // dp[i][0] and dp[i][1]
        int result = 1;
        
        for (int i = 1; i < n; i++) {
            int newDp0 = 1, newDp1 = 1;
            
            // Choose nums1[i]
            if (nums1[i] >= nums1[i-1]) {
                newDp0 = Math.Max(newDp0, dp0 + 1);
            }
            if (nums1[i] >= nums2[i-1]) {
                newDp0 = Math.Max(newDp0, dp1 + 1);
            }
            
            // Choose nums2[i]
            if (nums2[i] >= nums1[i-1]) {
                newDp1 = Math.Max(newDp1, dp0 + 1);
            }
            if (nums2[i] >= nums2[i-1]) {
                newDp1 = Math.Max(newDp1, dp1 + 1);
            }
            
            dp0 = newDp0;
            dp1 = newDp1;
            result = Math.Max(result, Math.Max(dp0, dp1));
        }
        
        return result;
    }
}

var maxNonDecreasingLength = function(nums1, nums2) {
    const n = nums1.length;
    let dp0 = 1, dp1 = 1;  // dp[i][0] and dp[i][1]
    let result = 1;
    
    for (let i = 1; i < n; i++) {
        let newDp0 = 1, newDp1 = 1;
        
        // Choose nums1[i]
        if (nums1[i] >= nums1[i-1]) {
            newDp0 = Math.max(newDp0, dp0 + 1);
        }
        if (nums1[i] >= nums2[i-1]) {
            newDp0 = Math.max(newDp0, dp1 + 1);
        }
        
        // Choose nums2[i]
        if (nums2[i] >= nums1[i-1]) {
            newDp1 = Math.max(newDp1, dp0 + 1);
        }
        if (nums2[i] >= nums2[i-1]) {
            newDp1 = Math.max(newDp1, dp1 + 1);
        }
        
        dp0 = newDp0;
        dp1 = newDp1;
        result = Math.max(result, dp0, dp1);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n)
空间复杂度O(1)
  • 时间复杂度：遍历数组一次，每次进行常数时间的状态转移操作
  • 空间复杂度：使用滚动数组优化，只需要常数个变量存储状态

相关题目