力扣2771题解析：双数组动态规划求解最长非递减子数组问题

一、题目解读

力扣2771题要求从两个整数数组nums1和nums2中合并元素，寻找最长非递减子数组的长度。非递减子数组指元素单调递增或相等的连续序列。题目难点在于需同时考虑两个数组的交互关系，找到全局最优解。

二、解题思路

动态规划（DP）策略。定义两个DP数组dp1[i]和dp2[i]，分别表示以nums1[i]和nums2[i]结尾的最长非递减子数组长度。核心在于利用双数组处理两数组的交叉选择：每个位置可视为选择当前数组元素或延续另一数组的前缀结果。通过状态转移方程更新最大值，最终取dp1和dp2中的全局最大值。

三、解题步骤

1. 初始化：dp1和dp2初始值均为1（单个元素即合法子数组）。

2. 迭代处理：

    若nums1[i]≥nums1[i-1]，则dp1[i]可延续dp1[i-1]；

    若nums1[i]≥nums2[i-1]，则dp1[i]可承接dp2[i-1]（跨数组合并）；

    同理处理dp2[i]的两种情况。

3. 全局更新：每次迭代后比较dp1[i]和dp2[i]，取最大值存入max_len。

4. 返回结果：max_len即为最终答案。

四、代码与注释

class Solution {
public:
    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        if (n == 0) return 0;
        
        // dp1[i]表示选择nums1[i]时的最长非递减子数组长度
        // dp2[i]表示选择nums2[i]时的最长非递减子数组长度
        vector<int> dp1(n, 1), dp2(n, 1);
        int max_len = 1;
        
        for (int i = 1; i < n; ++i) {
            // 当前选择nums1[i]的情况
            if (nums1[i] >= nums1[i-1]) {
                dp1[i] = max(dp1[i], dp1[i-1] + 1); // 延续nums1前缀
            }
            if (nums1[i] >= nums2[i-1]) {
                dp1[i] = max(dp1[i], dp2[i-1] + 1); // 跨数组合并
            }
            
            // 当前选择nums2[i]的情况
            if (nums2[i] >= nums1[i-1]) {
                dp2[i] = max(dp2[i], dp1[i-1] + 1);
            }
            if (nums2[i] >= nums2[i-1]) {
                dp2[i] = max(dp2[i], dp2[i-1] + 1); // 延续nums2前缀
            }
            
            // 更新全局最大值
            max_len = max(max_len, max(dp1[i], dp2[i]));
        }
        
        return max_len;
    }
};

五、总结

本解法通过双DP数组巧妙处理双数组交叉选择问题，时间复杂度O(n)，空间复杂度O(n)。动态规划的关键在于明确状态定义和转移逻辑，适用于需要全局最优解且存在重叠子问题的场景。理解两数组元素的“可衔接性”是解题核心。