3738. 替换至多一个元素后最长非递减子数组

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

考点

  • 状态机DP
  • 状态设计

思路

题意

给定整数数组 nums，允许至多一次将某个元素替换成任意整数。求最长的连续非递减子数组长度。

为什么“直接两状态 DP”会踩坑

直觉上容易写出如下朴素状态：

  • \(g_0[i]\)：以 \(a[i]\) 结尾，未修改的最长非递减子数组长度
  • \(g_1[i]\)：以 \(a[i]\) 结尾，已用一次修改的最长非递减子数组长度（修改位置任意）

然后尝试：

  • “不改 \(i\)”：若 \(a[i]\ge a[i-1]\)，则 \(g_1[i]=g_1[i-1]+1\)
  • “改 \(i\)”：\(g_1[i]=g_0[i-1]+1\)

问题在于：\(g_1[i-1]\) 里可能包含“把 \(a[i-1]\) 改掉”的方案，这时“能否接上 \(a[i]\)”取决于改后的值，而不是原值 \(a[i-1]\)。仅用长度做状态会丢失“末尾真实值”，从而产生错误延伸。

下面用最短反例直接说明。

⚠️ 反例：[1, 1, 0, 0] 会让朴素转移产生“不存在”的长度 4

记数组为 \(a=[1,1,0,0]\)。

  • 在位置 \(i=3\)（1-based 的第三个元素，值为 0）处“改 \(a[3]\)”可以得到长度 3： \([1,1,0]\) 把最后的 0 改成 1 得 \([1,1,1]\)。
  • 朴素 DP 会把这个长度 3 记进 \(g_1[3]=3\)。
  • 到 \(i=4\)（最后一个 0），朴素 DP 只看原数组 \(a[3]\le a[4]\) 即 \(0\le 0\)，于是做 \(g_1[4]=g_1[3]+1=4\)，声称全长 4 可行。

但真实情况：那条长度 3 的链的末尾是“改后的值 1”，要接上最后的 0 必须满足 \(1\le 0\)，不可能。 所以长度 4 根本不存在，朴素转移错误。

结论：*要想 \(O(n)\) 正确转移，必须让“已修改一次”的状态具备可延伸性，也就是保证*当前结尾元素没有被修改，从而末尾值可用原数组比较。

下标约定

为与实现一致，以下使用 1-based 记号：

  • 数组记为 \(a[1..n]\)，其中 \(a[i]=\text{nums}[i-1]\)。
  • DP 状态均表示“以第 \(i\) 个元素结尾”。

状态定义（可安全延伸版）

  • \(f_0[i]\)：以 \(a[i]\) 结尾，未使用修改 的最长非递减子数组长度。
  • \(f_1[i]\)：以 \(a[i]\) 结尾，已使用一次修改 的最长非递减子数组长度，并且满足： 结尾 \(a[i]\) 没有被修改（修改发生在更左侧，或发生在 \(a[i-1]\)）。

这条约束保证：当判断能否从 \(i-1\) 延伸到 \(i\) 时，只需比较原数组 \(a[i-1]\le a[i]\)。

初始值

\[ f_0[1]=1,\quad f_1[1]=1,\quad \text{ans}=1 \]

状态转移

1) 不修改：\(f_0[i]\)

\[ f_0[i]= \begin{cases} f_0[i-1]+1, & a[i]\ge a[i-1] \\ 1, & a[i]<a[i-1] \end{cases} \]

2) 使用一次修改且结尾未改：\(f_1[i]\)

先写一个必须存在的“兜底”：

对任意相邻两元素 \(a[i-1],a[i]\)，总可以通过一次修改把它们变为非递减（改前一个或后一个）。 因此对所有 \(i\ge 2\)，必有 \(f_1[i]\ge 2\)。

所以初始化： \[ f_1[i]\leftarrow 2\quad (i\ge 2) \] 随后考虑两种修改位置：

情况 A：修改发生在 \(\le i-2\)（尾部 \(a[i-1],a[i]\) 均为原值）

若 \(a[i]\ge a[i-1]\)，则可以从 \(f_1[i-1]\) 延伸： \[ \text{若 } a[i]\ge a[i-1],\quad f_1[i]=\max\bigl(f_1[i],\,f_1[i-1]+1\bigr) \]

情况 B：修改发生在 \(i-1\)（用它桥接 \(i-2\) 与 \(i\)）

尾部形状：

1
2
idx:    i-2   i-1    i
        o      X     o

需要存在替换值 \(x\) 使 \(a[i-2]\le x\le a[i]\)，等价于 \(a[i-2]\le a[i]\)。因此当 \(i\ge 3\) 且 \(a[i]\ge a[i-2]\)： \[ f_1[i]=\max\bigl(f_1[i],\,f_0[i-2]+2\bigr) \]

汇总：\(f_1[i]\)（\(i\ge 2\)）

\[ f_1[i]= \max\Bigl( 2,\; \mathbf{1}_{a[i]\ge a[i-1]}(f_1[i-1]+1),\; \mathbf{1}_{i\ge 3 \land a[i]\ge a[i-2]}(f_0[i-2]+2) \Bigr) \]

答案更新（必须额外考虑“修改在 i”）

若唯一一次修改用在当前位置 \(i\)，则左侧必须完全不改，最长可接长度为 \(f_0[i-1]\)，因此候选为： \[ \text{cand}_i=f_0[i-1]+1 \] 该候选的结尾被修改，不适合作为“可延伸状态”写回 \(f_1[i]\)，但必须用于更新全局答案： \[ \text{ans}=\max\bigl(\text{ans},\; f_0[i],\; f_1[i],\; f_0[i-1]+1\bigr) \]

点阵图

图 1：不修改延伸（\(f_0\)）

1
2
3
4
5
idx:        i-1    i
            o ---- o

条件：a[i-1] <= a[i]  则 f0[i] = f0[i-1] + 1
否则：断开            f0[i] = 1

图 2：修改在 ≤ i-2，从 f1[i-1] 延伸

1
2
3
4
5
idx:    ...  i-2   i-1    i
        ...   X     o ---- o

尾部 (i-1,i) 都是原值
条件：a[i-1] <= a[i]  则 f1[i] = f1[i-1] + 1

图 3：修改在 i-1，桥接 i-2 与 i

1
2
3
4
5
idx:    ...  i-2   i-1    i
        ...   o     X     o

条件：a[i-2] <= a[i]
转移：f1[i] = max(f1[i], f0[i-2] + 2)

图 4：修改在 i（只更新答案）

1
2
3
4
5
idx:        i-1    i
            o     X

候选：cand = f0[i-1] + 1
只用于更新 ans，不写回 f1[i]

AC代码（与公式逐条对应）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    const int maxn = 1e5 + 5;
    int longestSubarray(vector<int>& nums) {
        int f[2][maxn], n = (int)nums.size(), res = 1;

        // 1-based: i 表示“以第 i 个元素结尾”
        f[0][1] = 1;
        f[1][1] = 1;

        for (int i = 2; i <= n; ++i) {
            // f0[i]
            f[0][i] = (nums[i - 1] >= nums[i - 2]) ? f[0][i - 1] + 1 : 1;

            // f1[i] baseline: 任意相邻两数都可用一次修改变非递减
            f[1][i] = 2;

            // 修改在 <= i-2：从 f1[i-1] 延伸
            if (nums[i - 1] >= nums[i - 2]) {
                f[1][i] = max(f[1][i], f[1][i - 1] + 1);
            }

            // 修改在 i-1：桥接 i-2 与 i
            if (i >= 3 && nums[i - 1] >= nums[i - 3]) {
                f[1][i] = max(f[1][i], f[0][i - 2] + 2);
            }

            // 修改在 i：只进答案
            res = max(res, f[0][i - 1] + 1);

            // 不修改 / 修改不在 i
            res = max(res, f[0][i]);
            res = max(res, f[1][i]);
        }
        return res;
    }
};

当然也可以滚动数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    const int maxn = 1e5 + 5, neg = 0xcfcfcfcf;
    int longestSubarray(vector<int>& nums) {
        int n = nums.size(), res = 1, a0 = 0, b0 = neg, a1 = 1, b1 = 1;
        for (int i = 2; i <= n; ++i) {
            int a2, b2;
            a2 = nums[i - 1] >= nums[i - 2] ? a1 + 1 : 1, b2 = 2;
            if (nums[i - 1] >= nums[i - 2])
                b2 = b1 + 1;
            if (i >= 3 && nums[i - 1] >= nums[i - 3])
                b2 = max(b2, a0 + 2);
            res = max(res, max(a1 + 1, max(a2, b2)));
            a0 = a1, b0 = b1, a1 = a2, b1 = b2;
        }
        return res;
    }
};