深入理解 LeetCode 978：最长湍流子数组

深入理解 LeetCode 978：最长湍流子数组

目录

1. 问题描述
2. 示例解析
3. 解题思路
4. 代码实现
5. 代码详解
6. 时间与空间复杂度
7. 总结

问题描述

给定一个整数数组 arr，返回 arr 的 最大湍流子数组 的长度。

湍流子数组 的定义是：子数组中的元素与相邻元素的大小关系交替变化。

更正式地说，当子数组 A[i], A[i+1], ..., A[j] 满足以下条件时，我们称其为湍流子数组：

• 对于每个 k 满足 i ≤ k < j：
  • 如果 k 是奇数，A[k] > A[k+1] 且如果 k 是偶数，A[k] < A[k+1]；
  • 或者如果 k 是偶数，A[k] > A[k+1] 且如果 k 是奇数，A[k] < A[k+1]。

换句话说，子数组中的元素要么是 波浪式 增减交替，要么是 逆波浪式 增减交替。

示例

示例 1：

输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：最长的湍流子数组是 [4,2,10,7,8]，长度为 5。

示例 2：

输入：arr = [4,8,12,16]
输出：2
解释：任何两个相邻的元素都可以组成一个湍流子数组，长度为 2。

示例 3：

输入：arr = [100]
输出：1
解释：单个元素自身就是一个湍流子数组，长度为 1。

提示

• 1 <= arr.length <= 4 * 10^4
• 0 <= arr[i] <= 10^9

示例解析

让我们详细解析 示例 1：

输入：arr = [9,4,2,10,7,8,8,1,9]

我们需要找到最长的湍流子数组。遍历数组并比较相邻元素的大小关系：

1. 9 > 4 （递减）
2. 4 < 2 （递增）→ 不符合交替
3. 2 < 10 （递增）
4. 10 > 7 （递减）
5. 7 < 8 （递增）
6. 8 == 8 （相等）
7. 8 > 1 （递减）
8. 1 < 9 （递增）

最长的交替序列是 [4,2,10,7,8]，长度为 5。

解题思路

要解决这个问题，我们可以使用 滑动窗口 技术来遍历数组，并动态维护当前湍流子数组的左右边界。关键点如下：

1. 比较相邻元素的关系：我们需要记录当前相邻元素是递增还是递减。
2. 交替变化：如果当前的比较关系与前一次不同，则可以扩展当前的湍流子数组；否则，需要调整窗口的左边界。
3. 处理相等情况：如果相邻元素相等，则当前湍流子数组被打断，窗口需要重新开始。

具体步骤：

• 使用两个指针 left 和 right 来表示当前滑动窗口的左右边界。
• 使用一个变量 pre 来记录上一次的比较结果（递增或递减）。
• 遍历数组，通过比较 arr[right-1] 和 arr[right] 的关系来更新窗口，并记录最大长度。

代码实现

下面是 Python 语言的实现代码：

from typing import List

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n = len(arr)
        if n < 2:
            return n
        left, right = 0, 1
        pre = False
        res = 1
        while right < n:
            current = arr[right - 1] < arr[right]
            if right == 1 or current == pre:
                left = right - 1
            if arr[right - 1] == arr[right]:
                left = right
            right += 1
            res = max(res, right - left)
            pre = current
        return res

代码详解

让我们逐行分析这段代码：

from typing import List

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

• 行 4-6：首先获取数组的长度 n。如果数组长度小于2，直接返回 n，因为一个元素自身就是一个湍流子数组。

        left, right = 0, 1
        pre = False
        res = 1

• 行 7-9：
  • 初始化两个指针 left 和 right，分别指向窗口的左边界和右边界，初始值为 0 和 1。
  • pre 用于记录上一次相邻元素比较的结果，初始为 False。
  • res 用于记录最长湍流子数组的长度，初始为 1。

        while right < n:
            current = arr[right - 1] < arr[right]

• 行 10-11：
  • 使用 while 循环遍历数组，直到 right 达到数组末尾。
  • current 表示当前两个相邻元素的比较结果，True 表示递增，False 表示递减。

            if right == 1 or current == pre:
                left = right - 1

• 行 12-14：
  • 如果是第一次比较（right == 1），或者当前比较结果与前一次相同（current == pre），则需要更新窗口的左边界 left 为 right - 1，重新开始一个新的湍流子数组。

            if arr[right - 1] == arr[right]:
                left = right

• 行 15-16：
  • 如果当前两个相邻元素相等，湍流子数组被打断，更新 left 为 right，表示从当前位置重新开始寻找新的湍流子数组。

            right += 1
            res = max(res, right - left)
            pre = current

• 行 17-19：
  • 将 right 指针向右移动一位。
  • 更新 res 为当前窗口长度 right - left 和之前记录的最大值之间的较大值。
  • 将 pre 更新为 current，为下一次比较做准备。

        return res

• 行 20：返回记录的最长湍流子数组长度。

代码运行示例

让我们以 示例 1 [9,4,2,10,7,8,8,1,9] 为例，逐步分析代码执行过程：

1. 初始化：

   • left = 0
   • right = 1
   • pre = False
   • res = 1

2. 第一次迭代 (right = 1)：

   • 比较 9 和 4：9 > 4，所以 current = False
   • 因为 right == 1，更新 left = 0
   • 更新 res = max(1, 2 - 0) = 2
   • 更新 pre = False
   • right 增加到 2

3. 第二次迭代 (right = 2)：

   • 比较 4 和 2：4 > 2，所以 current = False
   • 因为 current == pre，更新 left = 1
   • 更新 res = max(2, 3 - 1) = 2
   • 更新 pre = False
   • right 增加到 3

4. 第三次迭代 (right = 3)：

   • 比较 2 和 10：2 < 10，所以 current = True
   • current != pre，不更新 left
   • 更新 res = max(2, 4 - 1) = 3
   • 更新 pre = True
   • right 增加到 4

5. 第四次迭代 (right = 4)：

   • 比较 10 和 7：10 > 7，所以 current = False
   • current != pre，不更新 left
   • 更新 res = max(3, 5 - 1) = 4
   • 更新 pre = False
   • right 增加到 5

6. 第五次迭代 (right = 5)：

   • 比较 7 和 8：7 < 8，所以 current = True
   • current != pre，不更新 left
   • 更新 res = max(4, 6 - 1) = 5
   • 更新 pre = True
   • right 增加到 6

7. 第六次迭代 (right = 6)：

   • 比较 8 和 8：8 == 8，所以 current = False
   • 因为 current == pre，更新 left = 5
   • 同时因为 arr[5] == arr[6]，再次更新 left = 6
   • 更新 res = max(5, 7 - 6) = 5
   • 更新 pre = False
   • right 增加到 7

8. 第七次迭代 (right = 7)：

   • 比较 8 和 1：8 > 1，所以 current = False
   • 因为 current == pre，更新 left = 6
   • 更新 res = max(5, 8 - 6) = 5
   • 更新 pre = False
   • right 增加到 8

9. 第八次迭代 (right = 8)：

   • 比较 1 和 9：1 < 9，所以 current = True
   • current != pre，不更新 left
   • 更新 res = max(5, 9 - 6) = 5
   • 更新 pre = True
   • right 增加到 9

循环结束，最终返回 res = 5。

时间与空间复杂度

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要一次遍历即可完成。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

总结

1. 记录相邻元素的比较关系，并确保其交替变化。
2. 动态调整窗口边界，以维护当前的湍流子数组。
3. 处理相等情况，确保窗口正确更新。