至多更改一个元素后的最长等差数列 - LeetCode-3872 解法

I’m happy to help translate the article, but I’ll need the full text you’d like translated. Could you please paste the content (or the portion you want translated) here? I’ll keep the source line unchanged and preserve all formatting as requested.

Source: …

最多更改一个元素后的最长等差子序列

Problem link: (add the actual link here)

我们给定一个整数数组 nums。
如果 子数组 中相邻元素的差值保持恒定，则该子数组是等差的。
我们可以将 至多一个 元素替换为任意整数。

目标： 返回在进行一次替换后能够得到的等差子数组的最大长度。

示例

Input:  nums = [9, 7, 5, 10, 1]
Output: 5

将 10 替换为 3 → [9, 7, 5, 3, 1]。
公差 = -2。长度 = 5。

为什么朴素的 O(N²) 解法行不通

显而易见的做法是：

1. 遍历每一个索引 i。
2. 尝试用一个符合相邻元素的值来替换 nums[i]。
3. 向左和向右扫描，寻找最长的等差子数组。

对每个索引都这样做的时间复杂度是 O(N²)，超出了 N ≤ 10⁵ 的限制。
我们需要一个 O(N) 的解法。

关键观察

我们替换的元素充当一个桥梁，可以连接：

• 在其左侧的一个有效等差数列，且
• 在其右侧的一个有效等差数列。

与其模拟每一次替换，我们预先计算两个辅助数组：

两个数组均在一次线性遍历中构建。

Source: …

如何使用 left 和 right

对于每个索引 i（我们可能要替换的元素），设

• l = i‑1（左侧邻居）
• r = i+1（右侧邻居）

我们有三种可能性：

1. 仅扩展左侧 – 将被替换的元素追加到以 l 结尾的序列中。
   len = left[l] + 1
2. 仅扩展右侧 – 将被替换的元素前置到以 r 开始的序列中。
   len = right[r] + 1
3. 桥接两侧 – 使 nums[i] 成为 nums[l] 与 nums[r] 之间的精确中间值。
   • 仅当 (nums[r] - nums[l]) 为 偶数 时才可行。
   • 所需的公差：diff = (nums[r] - nums[l]) / 2。
   • 如果左侧和右侧序列都具有该 diff，我们就可以通过 i 将它们合并。

桥接的长度从 3 开始（nums[l]、被替换的 nums[i]、nums[r]），并通过共享相同 diff 的左/右序列的长度进行扩展。

# left[i] = length of longest arithmetic subarray ending at i
left = [1] * n
for i in range(2, n):
    if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
        left[i] = left[i-1] + 1
    else:
        left[i] = 2          # start a new pair

# right[i] = length of longest arithmetic subarray starting at i
right = [1] * n
for i in range(n-3, -1, -1):
    if nums[i+1] - nums[i] == nums[i+2] - nums[i+1]:
        right[i] = right[i+1] + 1
    else:
        right[i] = 2          # start a new pair

两个循环的运行时间为 O(N)。

完整实现

Python

from typing import List

class Solution:
    def longestArithmetic(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return n

        # pre‑compute left and right arrays
        left = [1] * n
        for i in range(2, n):
            if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
                left[i] = left[i-1] + 1
            else:
                left[i] = 2

        right = [1] * n
        for i in range(n-3, -1, -1):
            if nums[i+1] - nums[i] == nums[i+2] - nums[i+1]:
                right[i] = right[i+1] + 1
            else:
                right[i] = 2

        ans = 2  # at least two elements form an arithmetic subarray

        # try changing each element
        for i in range(1, n-1):
            # case 1: extend left side only
            ans = max(ans, left[i-1] + 1)
            # case 2: extend right side only
            ans = max(ans, right[i+1] + 1)

            # case 3: bridge both sides
            if (nums[i+1] - nums[i-1]) % 2 == 0:
                diff = (nums[i+1] - nums[i-1]) // 2
                cur_len = 3
                # extend left while maintaining diff
                l = i-2
                while l >= 0 and nums[l+1] - nums[l] == diff:
                    cur_len += 1
                    l -= 1
                # extend right while maintaining diff
                r = i+2
                while r < n and nums[r] - nums[r-1] == diff:
                    cur_len += 1
                    r += 1
                ans = max(ans, cur_len)

        # edge cases: modify first or last element
        ans = max(ans, right[1] + 1)   # change nums[0]
        ans = max(ans, left[n-2] + 1)  # change nums[n-1]

        return ans

C++（原始发布）

// Note: The original snippet is incomplete; it is reproduced verbatim.
if (n  left(n, 2), right(n, 2);
left[0] = 1;               // only the first element
right[n-1] = 1;            // only the last element

// ----- left -----
for (int i = 2; i = 0; --i) {
    if (nums[i+1] - nums[i] == nums[i+2] - nums[i+1])
        right[i] = right[i+1] + 1;
}

int ans = 2;

// Edge cases: modify first or last element
ans = max(ans, right[1] + 1);          // change nums[0]
ans = max(ans, left[n-2] + 1);         // change nums[n-1]

// ----- try modifying each middle element -----
for (int i = 1; i  0 && (nums[l] - nums[l-1]) == diff)
            cur_len += left[l] - 1;      // left[l] already counts nums[l]

        if (r & nums) {

洞察

预先计算前缀/后缀状态并在每个索引处合并 在以下类型的问题中经常出现：

• 最多一次替换/删除
• 通过单个元素合并两个有效子数组
• 带有一次“免费通行”的滑动窗口变体

要点

每当看到“至多更改一个元素”时，考虑一下可以从左侧和右侧预先计算什么。