当前位置：首页 > article >正文

LeetCode 2765. 最长交替子数组解析与解题思路

article 2025/1/11 14:26:04

LeetCode 2765. 最长交替子数组解析与解题思路

在本篇博客中，我们将深入解析 LeetCode 上的一道有趣题目 —— 2765. 最长交替子数组。我们将通过题目理解、解题思路、代码实现以及示例解析，全面掌握这道题目的解决方法。

题目描述

给定一个下标从 0 开始的整数数组 nums，如果数组中长度为 m 的子数组 s 满足以下条件，我们称其为一个 交替子数组：

m 大于 1。
s1 = s0 + 1。
子数组 s 与数组 [s0, s1, s0, s1, ..., s(m-1) % 2] 一样。也就是说，s1 - s0 = 1，s2 - s1 = -1，s3 - s2 = 1，s4 - s3 = -1，以此类推，直到 s[m - 1] - s[m - 2] = (-1)^(m-1)。

请你返回 nums 中所有交替子数组中，最长的长度。如果不存在交替子数组，请返回 -1。

注意：

子数组是一个数组中一段连续非空的元素序列。

示例

示例 1：

输入：nums = [2,3,4,3,4]
输出：4
解释：交替子数组有 [2,3]，[3,4]，[3,4,3] 和 [3,4,3,4]。最长的子数组为 [3,4,3,4]，长度为 4。

示例 2：

输入：nums = [4,5,6]
输出：2
解释：[4,5] 和 [5,6] 是仅有的两个交替子数组。它们长度都为 2。

提示

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

解题思路

为了找到数组中最长的交替子数组，我们需要按照题目定义的条件进行检查。具体来说：

子数组长度大于1：我们只需要考虑长度至少为2的子数组。
相邻元素关系：第一个元素与第二个元素之间的差必须为1，即 s1 = s0 + 1。
交替关系：之后的元素需要交替地增减，即 s2 = s1 - 1，s3 = s2 + 1，以此类推。

基于上述条件，我们可以采用滑动窗口的方法，遍历数组，找到满足条件的最长子数组。

具体步骤

初始化答案 ans 为 -1，表示尚未找到满足条件的子数组。
使用指针 i 遍历数组，从第一个元素开始。
对于每一个位置 i，检查 nums[i+1] - nums[i] 是否等于1。如果不等于1，则继续移动指针。
如果满足 nums[i+1] - nums[i] == 1，则记录当前起始位置 i0。
然后，开始检查后续元素是否符合交替关系：
- 第三个元素 nums[i+2] 应该等于 nums[i]（即 nums[i+2] == nums[i]）。
- 第四个元素 nums[i+3] 应该等于 nums[i+1]，以此类推。
持续扩展子数组长度，直到不满足交替关系。
更新 ans 为当前找到的子数组长度与之前记录的最大值之间的较大者。
重复上述过程，直到遍历完整个数组。
最后返回 ans。

代码实现

以下是基于上述思路的 Python 代码实现：

class Solution:
    def alternatingSubarray(self, nums: List[int]) -> int:
        ans = -1
        i, n = 0, len(nums)
        while i < n - 1:
            # 检查当前和下一个元素是否满足差为1
            if nums[i + 1] - nums[i] != 1:
                i += 1
                continue
            # 记录当前起始位置
            i0 = i
            i += 2
            # 检查后续元素是否满足交替关系
            while i < n and nums[i - 2] == nums[i]:
                i += 1
            # 更新答案
            ans = max(ans, i - i0)
            # 回退一位，以防漏掉可能的子数组
            i -= 1
        return ans

代码解析

初始化：
- ans = -1：用于记录最长的交替子数组长度，初始设为 -1 表示尚未找到。
- i, n = 0, len(nums)：i 为当前遍历的索引，n 为数组长度。
主循环：
- while i < n - 1：遍历数组，确保至少有两个元素可以比较。
- if nums[i + 1] - nums[i] != 1：检查当前元素与下一个元素的差是否为1，不满足则移动指针 i。
找到可能的交替子数组起点：
- i0 = i：记录子数组的起始位置。
- i += 2：跳过下一个元素，准备检查更长的子数组。
检查交替关系：
- while i < n and nums[i - 2] == nums[i]：检查当前元素是否等于起始位置的元素，以维持交替关系。
- i += 1：如果满足条件，继续扩展子数组长度。
更新答案：
- ans = max(ans, i - i0)：更新最长子数组长度。
- i -= 1：回退一位，防止遗漏潜在的子数组。
返回结果：
- return ans：返回找到的最长交替子数组长度，如果没有则返回 -1。

示例解析

让我们通过示例来更好地理解算法的执行过程。

示例 1

输入：nums = [2,3,4,3,4]

步骤：

i = 0：
- nums[1] - nums[0] = 3 - 2 = 1，满足条件。
- i0 = 0，i = 2。
- 检查 nums[0] == nums[2] 即 2 == 4，不满足，停止扩展。
- 更新 ans = max(-1, 2 - 0) = 2。
i = 1：
- nums[2] - nums[1] = 4 - 3 = 1，满足条件。
- i0 = 1，i = 3。
- 检查 nums[1] == nums[3] 即 3 == 3，满足，i = 4。
- 检查 nums[2] == nums[4] 即 4 == 4，满足，i = 5（超出范围）。
- 更新 ans = max(2, 5 - 1) = 4。
遍历结束，返回 ans = 4。

结果：4

示例 2

输入：nums = [4,5,6]

步骤：

i = 0：
- nums[1] - nums[0] = 5 - 4 = 1，满足条件。
- i0 = 0，i = 2。
- 检查 nums[0] == nums[2] 即 4 == 6，不满足，停止扩展。
- 更新 ans = max(-1, 2 - 0) = 2。
i = 1：
- nums[2] - nums[1] = 6 - 5 = 1，满足条件。
- i0 = 1，i = 3（超出范围）。
- 更新 ans = max(2, 3 - 1) = 2。
遍历结束，返回 ans = 2。