最长交替子数组

标签: 数组 枚举

难度: Easy

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

  • m 大于 1 。
  • s1 = s0 + 1 。
  • 下标从 0 开始的子数组 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 。

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

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

示例 1：

输入：nums = [2,3,4,3,4]
输出：4
解释：交替子数组有 [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] <= 104

Submission

运行时间: 22 ms

内存: 16.1 MB

class Solution:
    def alternatingSubarray(self, nums: List[int]) -> int:
        a, b = nums[:2]
        cnt = max_cnt = (b == a + 1) * 2
        for x in nums[2:]:
            if cnt > 0 and x == a:
                a, b = b, a
                cnt += 1
            else:
                max_cnt = max(cnt, max_cnt)
                a, b = b, x
                cnt = (b ==  a + 1) * 2
                max_cnt = max(cnt, max_cnt)
        max_cnt = max(cnt, max_cnt)
        return max_cnt or -1

Explain

该题解采用双指针策略来检测并统计最长的交替子数组。首先初始化两个指针a和b，分别代表交替子数组的当前两个连续元素。变量cnt用于记录当前交替子数组的长度，而max_cnt用于记录遇到的最长交替子数组的长度。接下来，遍历数组中的每个元素，检查当前元素是否能延续当前的交替模式。如果可以，则更新a，b和cnt。如果不可以，就将当前的cnt与max_cnt比较，更新max_cnt，并尝试重新开始一个新的交替子数组。循环结束后，再次比较cnt和max_cnt确保最后一个可能的子数组被正确处理。如果max_cnt仍为0，说明没有找到合适的交替子数组，返回-1。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def alternatingSubarray(self, nums: List[int]) -> int:
        a, b = nums[:2]  # 初始化前两个元素
        cnt = max_cnt = (b == a + 1) * 2  # 初始化计数器和最大长度计数器
        for x in nums[2:]:  # 从第三个元素开始遍历
            if cnt > 0 and x == a:  # 如果当前元素能继续交替模式
                a, b = b, a  # 更新a和b
                cnt += 1  # 增加当前交替子数组的长度
            else:  # 如果不能继续交替模式
                max_cnt = max(cnt, max_cnt)  # 更新最大交替子数组长度
                a, b = b, x  # 重新开始新的交替子数组
                cnt = (b == a + 1) * 2  # 重置计数器
                max_cnt = max(cnt, max_cnt)  # 再次更新最大长度
        max_cnt = max(cnt, max_cnt)  # 确保最后一个子数组被处理
        return max_cnt or -1  # 如果没有有效交替子数组，返回-1

Explore

在双指针策略中，a和b作为指针主要用于追踪交替子数组中的最后两个元素。它们帮助确定当前数组元素是否与前一个元素交替（即符合交替模式的递增或递减关系）。当当前元素符合与前一个元素的交替模式时，指针a和b的值会更新，以此延续并记录当前的交替子数组。如果当前元素不符合交替模式，指针a和b则会重置，以尝试在新的位置开始识别新的交替子数组。

在题解中，当前元素x被认为可以继续交替模式的条件是x等于前一个元素a。这意味着x能够与前一个元素a形成有效的交替关系（例如，如果前一个元素是递增的下一个元素，则当前元素应为递增后的值），从而可以继续当前的交替子数组。当这种情况发生时，a和b的值会更新，其中a变为b，b变为x，以此继续扩展交替子数组的长度。

当当前元素x不能继续交替模式时，代码首先会比较并更新max_cnt，以记录到目前为止找到的最长交替子数组的长度。然后，a和b的值会更新为最近的b和当前的x，尝试重新开始一个新的交替子数组。同时，cnt会重置为2（如果b和x满足交替条件），表示新子数组的初始长度。这种方法在每次发现当前元素无法继续交替子数组时重新开始计数，并更新最大长度，可以有效确保不遗漏任何可能的交替子数组。

当数组中的数字都相同时，例如nums = [5, 5, 5, 5]，算法会返回-1。这是因为所有元素都相同，无法形成任何交替模式。算法在这种情况下的处理是合理的，因为交替子数组的定义要求元素之间必须交替（即有递增或递减的关系），相同的元素之间无法形成这种关系。