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

胡志明t

一、题目解读

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

二、解题思路

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

三、解题步骤

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

2. 迭代处理：

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

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

    同理处理dp2的两种情况。

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

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

四、代码与注释

1. class Solution {
   
2. public:
   
3.     int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
   
4.         int n = nums1.size();
   
5.         if (n == 0) return 0;
   
6.         
   
7.         // dp1[i]表示选择nums1[i]时的最长非递减子数组长度
   
8.         // dp2[i]表示选择nums2[i]时的最长非递减子数组长度
   
9.         vector<int> dp1(n, 1), dp2(n, 1);
   
10.         int max_len = 1;
    
11.         
    
12.         for (int i = 1; i < n; ++i) {
    
13.             // 当前选择nums1[i]的情况
    
14.             if (nums1[i] >= nums1[i-1]) {
    
15.                 dp1[i] = max(dp1[i], dp1[i-1] + 1); // 延续nums1前缀
    
16.             }
    
17.             if (nums1[i] >= nums2[i-1]) {
    
18.                 dp1[i] = max(dp1[i], dp2[i-1] + 1); // 跨数组合并
    
19.             }
    
20.             
    
21.             // 当前选择nums2[i]的情况
    
22.             if (nums2[i] >= nums1[i-1]) {
    
23.                 dp2[i] = max(dp2[i], dp1[i-1] + 1);
    
24.             }
    
25.             if (nums2[i] >= nums2[i-1]) {
    
26.                 dp2[i] = max(dp2[i], dp2[i-1] + 1); // 延续nums2前缀
    
27.             }
    
28.             
    
29.             // 更新全局**值
    
30.             max_len = max(max_len, max(dp1[i], dp2[i]));
    
31.         }
    
32.         
    
33.         return max_len;
    
34.     }
    
35. };

复制代码

五、总结

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

来源：动态规划