3872. 最多修改一个元素后的最长等差数列

Medium

题目描述

给你一个整数数组 nums。

如果子数组中连续元素之间的差值是常数，则该子数组是等差数列。

你可以将 nums 中最多一个元素替换为任意整数。然后，从 nums 中选择一个等差子数组。

返回你能选择的等差子数组的最大长度。

示例 1：

输入：nums = [9,7,5,10,1]
输出：5
解释：
将 nums[3] = 10 替换为 3。数组变为 [9, 7, 5, 3, 1]。
选择子数组 [9, 7, 5, 3, 1]，它是等差数列，因为连续元素的公差为 -2。

示例 2：

输入：nums = [1,2,6,7]
输出：3
解释：
将 nums[0] = 1 替换为 -2。数组变为 [-2, 2, 6, 7]。
选择子数组 [-2, 2, 6, 7]，它是等差数列，因为连续元素的公差为 4。

约束条件：

4 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

解题思路

这道题的核心思想是预处理每个位置的左右等差数列长度，然后枚举替换位置来计算最大长度。

主要思路：

预处理左侧等差数列长度：计算以每个位置结尾的最长等差数列长度 L[i]
预处理右侧等差数列长度：计算从每个位置开始的最长等差数列长度 R[i]
枚举替换位置：对于每个可能的替换位置 i，考虑以下情况：
- 不替换任何元素，直接取最长的等差数列
- 替换位置 i，使得左侧以 i-1 结尾和右侧从 i+1 开始的等差数列能够连接
- 只扩展左侧或只扩展右侧

关键点：

当替换位置 i 时，需要检查 nums[i-1] 和 nums[i+1] 是否能形成公差为 (nums[i+1] - nums[i-1]) / 2 的等差数列
公差必须是整数，即 (nums[i+1] - nums[i-1]) 必须是偶数
最终答案是所有可能情况的最大值

时间复杂度为 O(n)，空间复杂度为 O(n)，这是一个高效的解法。

代码实现

class Solution {
public:
    int longestArithmetic(vector<int>& nums) {
        int n = nums.size();
        vector<int> L(n, 1), R(n, 1);
        
        // 计算 L[i]: 以位置 i 结尾的最长等差数列长度
        for (int i = 1; i < n; i++) {
            if (i > 1 && nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                L[i] = L[i-1] + 1;
            } else {
                L[i] = 2;
            }
        }
        
        // 计算 R[i]: 从位置 i 开始的最长等差数列长度
        for (int i = n-2; i >= 0; i--) {
            if (i < n-2 && nums[i+1] - nums[i] == nums[i+2] - nums[i+1]) {
                R[i] = R[i+1] + 1;
            } else {
                R[i] = 2;
            }
        }
        
        int maxLen = *max_element(L.begin(), L.end());
        
        // 枚举替换位置
        for (int i = 1; i < n-1; i++) {
            // 检查是否能连接左右两部分
            if ((nums[i+1] - nums[i-1]) % 2 == 0) {
                int expectedDiff = (nums[i+1] - nums[i-1]) / 2;
                int leftLen = 1, rightLen = 1;
                
                if (i > 1 && nums[i-1] - nums[i-2] == expectedDiff) {
                    leftLen = L[i-1];
                }
                if (i < n-2 && nums[i+2] - nums[i+1] == expectedDiff) {
                    rightLen = R[i+1];
                }
                
                maxLen = max(maxLen, leftLen + rightLen + 1);
            }
            
            // 只扩展左侧
            if (i > 1) {
                maxLen = max(maxLen, L[i-1] + 2);
            }
            
            // 只扩展右侧
            if (i < n-2) {
                maxLen = max(maxLen, R[i+1] + 2);
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestArithmetic(self, nums: List[int]) -> int:
        n = len(nums)
        L = [1] * n
        R = [1] * n
        
        # 计算 L[i]: 以位置 i 结尾的最长等差数列长度
        for i in range(1, n):
            if i > 1 and nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
                L[i] = L[i-1] + 1
            else:
                L[i] = 2
        
        # 计算 R[i]: 从位置 i 开始的最长等差数列长度
        for i in range(n-2, -1, -1):
            if i < n-2 and nums[i+1] - nums[i] == nums[i+2] - nums[i+1]:
                R[i] = R[i+1] + 1
            else:
                R[i] = 2
        
        max_len = max(L)
        
        # 枚举替换位置
        for i in range(1, n-1):
            # 检查是否能连接左右两部分
            if (nums[i+1] - nums[i-1]) % 2 == 0:
                expected_diff = (nums[i+1] - nums[i-1]) // 2
                left_len = 1
                right_len = 1
                
                if i > 1 and nums[i-1] - nums[i-2] == expected_diff:
                    left_len = L[i-1]
                if i < n-2 and nums[i+2] - nums[i+1] == expected_diff:
                    right_len = R[i+1]
                
                max_len = max(max_len, left_len + right_len + 1)
            
            # 只扩展左侧
            if i > 1:
                max_len = max(max_len, L[i-1] + 2)
            
            # 只扩展右侧
            if i < n-2:
                max_len = max(max_len, R[i+1] + 2)
        
        return max_len

public class Solution {
    public int LongestArithmetic(int[] nums) {
        int n = nums.Length;
        int[] L = new int[n];
        int[] R = new int[n];
        Array.Fill(L, 1);
        Array.Fill(R, 1);
        
        // 计算 L[i]: 以位置 i 结尾的最长等差数列长度
        for (int i = 1; i < n; i++) {
            if (i > 1 && nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                L[i] = L[i-1] + 1;
            } else {
                L[i] = 2;
            }
        }
        
        // 计算 R[i]: 从位置 i 开始的最长等差数列长度
        for (int i = n-2; i >= 0; i--) {
            if (i < n-2 && nums[i+1] - nums[i] == nums[i+2] - nums[i+1]) {
                R[i] = R[i+1] + 1;
            } else {
                R[i] = 2;
            }
        }
        
        int maxLen = L.Max();
        
        // 枚举替换位置
        for (int i = 1; i < n-1; i++) {
            // 检查是否能连接左右两部分
            if ((nums[i+1] - nums[i-1]) % 2 == 0) {
                int expectedDiff = (nums[i+1] - nums[i-1]) / 2;
                int leftLen = 1, rightLen = 1;
                
                if (i > 1 && nums[i-1] - nums[i-2] == expectedDiff) {
                    leftLen = L[i-1];
                }
                if (i < n-2 && nums[i+2] - nums[i+1] == expectedDiff) {
                    rightLen = R[i+1];
                }
                
                maxLen = Math.Max(maxLen, leftLen + rightLen + 1);
            }
            
            // 只扩展左侧
            if (i > 1) {
                maxLen = Math.Max(maxLen, L[i-1] + 2);
            }
            
            // 只扩展右侧
            if (i < n-2) {
                maxLen = Math.Max(maxLen, R[i+1] + 2);
            }
        }
        
        return maxLen;
    }
}

var longestArithmetic = function(nums) {
    const n = nums.length;
    const L = new Array(n).fill(1);
    const R = new Array(n).fill(1);
    
    // 计算 L[i]: 以位置 i 结尾的最长等差数列长度
    for (let i = 1; i < n; i++) {
        if (i > 1 && nums[i] - nums[i-1]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n)	需要遍历数组三次：计算L数组、R数组和枚举替换位置
空间复杂度	O(n)	需要额外的L和R数组存储每个位置的等差数列长度

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析