2771. 构造最长非递减子数组

发表于 分类于 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

  • 状态机DP

思路

一、问题抽象

给定两个长度为 \(n\) 的数组： \[ \text{nums1}[0 \ldots n-1], \quad \text{nums2}[0 \ldots n-1] \] 我们需要构造一个数组 \(\text{nums3}\)，满足：

  • 对每个位置 \(i\)，\(\text{nums3}[i]\) 只能选 \(\text{nums1}[i]\) 或 \(\text{nums2}[i]\)
  • \(\text{nums3}\) 的某个连续子数组是非递减的
  • 目标是该非递减连续子数组的最大长度

二、状态定义（DP State）

这是一个按位置 + 按选择来源分类的 DP。

定义： \[ f[i][0] = \text{以第 } i \text{ 个位置结尾，且 } \text{nums3}[i] = \text{nums1}[i-1] \text{ 时的最长非递减子数组长度} \]

说明：

  • 这里使用 1-based 的 DP 下标（与你代码一致）
  • 实际数组访问仍然是 nums?[i-1]

三、初始值（Initialization）

1. 为什么初始值是 1？

无论是否能与前一个位置形成非递减关系：

  • 单独的一个元素本身就构成长度为 1 的非递减子数组

因此： \[ f[i][0] \ge 1,\quad f[i][1] \ge 1 \]

2. 边界初始化

对于第一个位置： \[ f[1][0] = 1,\quad f[1][1] = 1 \] 对应代码：

1
f[1][0] = f[1][1] = 1;

四、状态转移（Transition）

对于任意 \(i \ge 2\)，我们考虑当前位置选哪个数组的元素。

情况一：当前位置选 nums1[i-1]（计算 \(f[i][0]\)）

默认不能延续任何子数组： \[ f[i][0] = 1 \] 然后尝试从前一位置延续：

1️⃣ 前一位也选 nums1

如果满足非递减条件： \[ \text{nums1}[i-1] \ge \text{nums1}[i-2] \] 则可以从 \(f[i-1][0]\) 延续： \[ f[i][0] = \max(f[i][0],\; f[i-1][0] + 1) \]

2️⃣ 前一位选 nums2

如果： \[ \text{nums1}[i-1] \ge \text{nums2}[i-2] \] 则可以从 \(f[i-1][1]\) 延续： \[ f[i][0] = \max(f[i][0],\; f[i-1][1] + 1) \]

情况二：当前位置选 nums2[i-1]（计算 \(f[i][1]\)）

同理：

初始化： \[ f[i][1] = 1 \]

1️⃣ 前一位选 nums1

\[ \text{nums2}[i-1] \ge \text{nums1}[i-2] \Rightarrow f[i][1] = \max(f[i][1],\; f[i-1][0] + 1) \]

2️⃣ 前一位选 nums2

\[ \text{nums2}[i-1] \ge \text{nums2}[i-2] \Rightarrow f[i][1] = \max(f[i][1],\; f[i-1][1] + 1) \]

代码与数学一一对应

1
2
3
4
5
6
7
8
9
10
11
f[i][0] = 1;
if (nums1[i - 1] >= nums1[i - 2])
    f[i][0] = max(f[i][0], f[i - 1][0] + 1);
if (nums1[i - 1] >= nums2[i - 2])
    f[i][0] = max(f[i][0], f[i - 1][1] + 1);

f[i][1] = 1;
if (nums2[i - 1] >= nums1[i - 2])
    f[i][1] = max(f[i][1], f[i - 1][0] + 1);
if (nums2[i - 1] >= nums2[i - 2])
    f[i][1] = max(f[i][1], f[i - 1][1] + 1);

五、答案的维护（Result）

因为最长非递减子数组可能在任意位置结束，并且结尾可能选 nums1 或 nums2： \[ \text{答案} = \max_{1 \le i \le n} \{ f[i][0], f[i][1] \} \] 在代码中边转移边维护：

1
2
res = max(res, f[i][0]);
res = max(res, f[i][1]);

六、复杂度分析

  • 时间复杂度： \[ O(n) \] 每个位置只进行常数次比较

  • 空间复杂度： \[ O(n) \] （可进一步压缩到 \(O(1)\)，只保留上一行）

七、DP 思想总结

这道题的核心在于：

“同一个位置，有两种状态；是否能延续，取决于前一位置选了什么。”

因此：

  • 状态必须区分「当前位置选 nums1 / nums2」
  • 每个状态都要尝试从前一位置的两种来源转移
  • 初始值统一为 1，表示“从当前位置重新开始”

这是一个典型的「双状态线性 DP」模板题。

八、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    static const int maxn = 1e5 + 5;
    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
        int f[maxn][2], n = nums1.size(), res = 1;
        f[1][0] = f[1][1] = 1;
        for (int i = 2; i <= n; ++i) {
            f[i][0] = 1;
            if (nums1[i - 1] >= nums1[i - 2])
                f[i][0] = max(f[i][0], f[i - 1][0] + 1);
            if (nums1[i - 1] >= nums2[i - 2])
                f[i][0] = max(f[i][0], f[i - 1][1] + 1);
            res = max(res, f[i][0]);
            f[i][1] = 1;
            if (nums2[i - 1] >= nums1[i - 2])
                f[i][1] = max(f[i][1], f[i - 1][0] + 1);
            if (nums2[i - 1] >= nums2[i - 2])
                f[i][1] = max(f[i][1], f[i - 1][1] + 1);
            res = max(res, f[i][1]);
        }
        return res;
    }
};

当然也可以滚动数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    static const int maxn = 1e5 + 5;
    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), res = 1, a = 1, b = 1;
        for (int i = 2; i <= n; ++i) {
            int ta = 1, tb = 1;
            ta = 1;
            if (nums1[i - 1] >= nums1[i - 2])
                ta = max(ta, a + 1);
            if (nums1[i - 1] >= nums2[i - 2])
                ta = max(ta, b + 1);
            res = max(res, ta);
            tb = 1;
            if (nums2[i - 1] >= nums1[i - 2])
                tb = max(tb, a + 1);
            if (nums2[i - 1] >= nums2[i - 2])
                tb = max(tb, b + 1);
            res = max(res, tb);
            a = ta, b = tb;
        }
        return res;
    }
};