Txing

欢迎来到 | 伽蓝之堂

0%

Q978 最长湍流子数组-中等-动态规划

Posted on In
Symbols count in article: 2.6k Reading time ≈ 2 mins.
Q978 最长湍流子数组-中等-动态规划

978. 最长湍流子数组

Question

当 A 的子数组 A[i], A[i+1], ..., A[j] 满足下列条件时，我们称其为湍流子数组：

若 i <= k < j，当 k 为奇数时， A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]； 或 若 i <= k < j，当 k 为偶数时，A[k] > A[k+1] ，且当 k 为奇数时， A[k] < A[k+1]。 也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。

返回 A 的最大湍流子数组的长度。

Example 1:

输入：[9,4,2,10,7,8,8,1,9] 输出：5 解释：(A[1] > A[2] < A[3] > A[4] < A[5])

Example 2:

输入：[4,8,12,16] 输出：2

提示：

  • 1 <= A.length <= 40000
  • 0 <= A[i] <= 10^9

Approach 1: 滑动窗口法

本题目需要仔细考虑清楚集中边界条件的情况：

  • 左右边界相等；
  • 右边界元素等于右边界+1元素；
  • 右边界什么时候右移
  • 左边界什么时候右移，移动到哪个位置

通过令边界left=right=0，设计一个滑动窗口，

  • 当左右边界相等时，此时子数组只包含一个元素，肯定是可以右边界右移的；
  • 当左右边界不相等时，如果右边界-1的元素、右边界元素、右边界+1的元素，三者满足或者时，右边界右移；
  • 当左右边界不相等时，如果右边界-1的元素、右边界元素、右边界+1的元素，三者不满足或者，则结束判断，left边界从right边界重新开始判断下一个子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def maxTurbulenceSize(self, arr) -> int:
        n = len(arr)
        res = 1
        left,right=0,0

        while(right<n-1):
            if left == right:
                # 右边界元素等于右边界+1的元素
                if arr[right] == arr[right+1]:
                    left+=1
                right+=1
            else:
                # 在扩展长度时候，只考虑验证右边界条件即可
                if (arr[right - 1] < arr[right]) and (arr[right] > arr[right + 1]):
                    right+=1
                elif (arr[right - 1] > arr[right]) and (arr[right] < arr[right + 1]):
                    right+=1
                else:
                # 右边界不符合条件则验证结束，将left右移，重新验证
                    left = right
            res = max(res, right - left + 1)

        return res


def main():
    inputs = [9,4,2,10,7,8,8,1,9]
    solution=Solution().maxTurbulenceSize(inputs)
    print(solution)


if __name__ == "__main__":
    main()

复杂度分析

  • 时间复杂度：，窗口的左右端点最多各移动 n 次。
  • 空间复杂度：，只需要维护常数额外空间。

Approach 2: 动态规划方法

也可以使用动态规划的方法计算最长湍流子数组的长度。

利用二维数组记录相邻元素的信息：

表示以arr[i]为结尾的，且的湍流子数组的最大长度。 表示以arr[i]为结尾的，且的湍流子数组的最大长度。 每次记录湍流子数组应该从1开始，因为需要包含自身。 - 当时，湍流子数组长度为，同时 - 当时，湍流子数组长度为，同时 - 当时，湍流子数组长度为 最终，数组的最大值即为所求的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def maxTurbulenceSize1(self, arr) -> int:
    n = len(arr)
    dp = [[0 for i in range(2)] for j in range(n)]
    dp[0][0] = dp[0][1] = 1
    for i in range(n):
        if arr[i-1] > arr[i]:
            dp[i][0] = dp[i-1][1] + 1
            dp[i][1] = 1
        elif arr[i-1] < arr[i]:
            dp[i][1] = dp[i-1][0] + 1
            dp[i][0] = 1
        else:
            dp[i][0] = dp[i][1] = 1

    res = 1
    for i in range(n):
        res = max(res, dp[i][0])
        res = max(res, dp[i][1])

    return res

复杂度分析

  • 时间复杂度：，遍历一遍数组。
  • 空间复杂度：，只需要维护dp。

其实还可以直接用两个变量和代替二维数组dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def maxTurbulenceSize2(self, arr) -> int:
    n = len(arr)
    res = 1
    dp0 = dp1 = 1
    # 注意要从1开始循环
    for i in range(1,n):
        if arr[i-1] > arr[i]:
            dp0 = dp1 + 1
            dp1 = 1
        elif arr[i-1] < arr[i]:
            dp1 = dp0 + 1
            dp0 = 1
        else:
            dp0 = dp1 = 1

        res = max(res, dp0)
        res = max(res, dp1)

    return res

复杂度分析

  • 时间复杂度：，遍历一遍数组。
  • 空间复杂度：，只需要维护dp0和dp1两个变量。