Hard

题目描述

给你一个整数数组 nums。

如果子数组 nums[l..r] 满足以下条件之一，则称其为交替的：

  • nums[l] < nums[l + 1] > nums[l + 2] < nums[l + 3] > ...
  • nums[l] > nums[l + 1] < nums[l + 2] > nums[l + 3] < ...

换句话说，如果我们比较子数组中的相邻元素，那么比较结果在严格大于和严格小于之间交替。

你可以从 nums 中删除最多一个元素。然后，你需要从 nums 中选择一个交替子数组。

返回你可以选择的交替子数组的最大长度。

长度为 1 的子数组被认为是交替的。

示例 1：

输入：nums = [2,1,3,2]
输出：4
解释：
选择不删除元素。
选择整个数组 [2, 1, 3, 2]，它是交替的，因为 2 > 1 < 3 > 2。

示例 2：

输入：nums = [3,2,1,2,3,2,1]
输出：4
解释：
选择删除 nums[3]，即 [3, 2, 1, 2, 3, 2, 1]。数组变为 [3, 2, 1, 3, 2, 1]。
选择子数组 [3, 2, 1, 3, 2, 1]。

示例 3：

输入：nums = [100000,100000]
输出：1
解释：
选择不删除元素。
选择子数组 [100000, 100000]。

提示：

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

解题思路

这道题要求我们删除最多一个元素后，找到最长的交替子数组。我们可以用动态规划的思路来解决。

核心思路：

  1. 定义状态：定义 left[i][d] 表示以位置 i 结尾的最长交替子数组长度，其中 d=0 表示最后一个比较是 <，d=1 表示最后一个比较是 >。类似地，定义 right[i][d] 表示从位置 i 开始的最长交替子数组长度。

  2. 预处理：从左到右计算 left 数组，从右到左计算 right 数组。如果相邻元素相等，交替链必须重新开始，因为 == 是无效的。

  3. 枚举删除：尝试删除每个位置 r 的元素：

    • 如果 nums[r-1] < nums[r+1]，两边可以用模式 < > 连接，长度为 left[r-1][0] + right[r+1][1]
    • 如果 nums[r-1] > nums[r+1]，两边可以用模式 > < 连接，长度为 left[r-1][1] + right[r+1][0]

  4. 不删除的情况：也要考虑不删除任何元素的情况，取所有 left[i][d] 的最大值。

时间复杂度：O(n)，其中 n 是数组长度。我们需要遍历数组三次：计算 left、right 和枚举删除位置。

空间复杂度：O(n)，用于存储 left 和 right 数组。

代码实现

class Solution {
public:
    int longestAlternating(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> left(n, vector<int>(2, 1));
        vector<vector<int>> right(n, vector<int>(2, 1));
        
        // 计算left数组：以i结尾的最长交替子数组
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i-1]) {
                left[i][1] = left[i-1][0] + 1;
            }
            if (nums[i] < nums[i-1]) {
                left[i][0] = left[i-1][1] + 1;
            }
        }
        
        // 计算right数组：从i开始的最长交替子数组
        for (int i = n-2; i >= 0; i--) {
            if (nums[i] > nums[i+1]) {
                right[i][1] = right[i+1][0] + 1;
            }
            if (nums[i] < nums[i+1]) {
                right[i][0] = right[i+1][1] + 1;
            }
        }
        
        int result = 1;
        
        // 不删除任何元素的情况
        for (int i = 0; i < n; i++) {
            result = max(result, max(left[i][0], left[i][1]));
        }
        
        // 尝试删除每个位置的元素
        for (int r = 1; r < n-1; r++) {
            if (nums[r-1] < nums[r+1]) {
                result = max(result, left[r-1][0] + right[r+1][1]);
            }
            if (nums[r-1] > nums[r+1]) {
                result = max(result, left[r-1][1] + right[r+1][0]);
            }
        }
        
        return result;
    }
};

class Solution:
    def longestAlternating(self, nums: List[int]) -> int:
        n = len(nums)
        left = [[1, 1] for _ in range(n)]
        right = [[1, 1] for _ in range(n)]
        
        # 计算left数组：以i结尾的最长交替子数组
        for i in range(1, n):
            if nums[i] > nums[i-1]:
                left[i][1] = left[i-1][0] + 1
            if nums[i] < nums[i-1]:
                left[i][0] = left[i-1][1] + 1
        
        # 计算right数组：从i开始的最长交替子数组
        for i in range(n-2, -1, -1):
            if nums[i] > nums[i+1]:
                right[i][1] = right[i+1][0] + 1
            if nums[i] < nums[i+1]:
                right[i][0] = right[i+1][1] + 1
        
        result = 1
        
        # 不删除任何元素的情况
        for i in range(n):
            result = max(result, max(left[i][0], left[i][1]))
        
        # 尝试删除每个位置的元素
        for r in range(1, n-1):
            if nums[r-1] < nums[r+1]:
                result = max(result, left[r-1][0] + right[r+1][1])
            if nums[r-1] > nums[r+1]:
                result = max(result, left[r-1][1] + right[r+1][0])
        
        return result

public class Solution {
    public int LongestAlternating(int[] nums) {
        int n = nums.Length;
        int[,] left = new int[n, 2];
        int[,] right = new int[n, 2];
        
        // 初始化
        for (int i = 0; i < n; i++) {
            left[i, 0] = left[i, 1] = 1;
            right[i, 0] = right[i, 1] = 1;
        }
        
        // 计算left数组：以i结尾的最长交替子数组
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i-1]) {
                left[i, 1] = left[i-1, 0] + 1;
            }
            if (nums[i] < nums[i-1]) {
                left[i, 0] = left[i-1, 1] + 1;
            }
        }
        
        // 计算right数组：从i开始的最长交替子数组
        for (int i = n-2; i >= 0; i--) {
            if (nums[i] > nums[i+1]) {
                right[i, 1] = right[i+1, 0] + 1;
            }
            if (nums[i] < nums[i+1]) {
                right[i, 0] = right[i+1, 1] + 1;
            }
        }
        
        int result = 1;
        
        // 不删除任何元素的情况
        for (int i = 0; i < n; i++) {
            result = Math.Max(result, Math.Max(left[i, 0], left[i, 1]));
        }
        
        // 尝试删除每个位置的元素
        for (int r = 1; r < n-1; r++) {
            if (nums[r-1] < nums[r+1]) {
                result = Math.Max(result, left[r-1, 0] + right[r+1, 1]);
            }
            if (nums[r-1] > nums[r+1]) {
                result = Math.Max(result, left[r-1, 1] + right[r+1, 0]);
            }
        }
        
        return result;
    }
}

var longestAlternating = function(nums) {
    const n = nums.length;
    const left = Array.from({length: n}, () => [1, 1]);
    const right = Array.from({length: n}, () => [1, 1]);
    
    // 计算left数组：以i结尾的最长交替子数组
    for (let i = 1; i < n; i++) {
        if (nums[i] > nums[i-1]) {
            left[i][1] = left[i-1][0] + 1;
        }
        if (nums[i] < nums[i-1]) {
            left[i][0] = left[i-1][1] + 1;
        }
    }
    
    // 计算right数组：从i开始的最长交替子数组
    for (let i = n-2; i >= 0; i--) {
        if (nums[i] > nums[i+1]) {
            right[i][1] = right[i+1][0] + 1;
        }
        if (nums[i] < nums[i+1]) {
            right[i][0] = right[i+1][1] + 1;
        }
    }
    
    let result = 1;
    
    // 不删除任何元素的情况
    for (let i = 0; i < n; i++) {
        result = Math.max(result, Math.max(left[i][0], left[i][1]));
    }
    
    // 尝试删除每个位置的元素
    for (let r = 1; r < n-1; r++) {
        if (nums[r-1] < nums[r+1]) {
            result = Math.max(result, left[r-1][0] + right[r+1][1]);
        }
        if (nums[r-1] > nums[r+1]) {
            result = Math.max(result, left[r-1][1] + right[r+1][0]);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(n)