HiJ's notebook

LeetCode-978.最长湍流子数组

字数统计: 439阅读时长: 2 min
2019/03/31 Share

[LeetCode]978

动态规划

题目描述

当 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 的最大湍流子数组的长度。
示例 1:

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

示例 2:

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

示例 3:

输入:[100]
输出:1

思路

用动态规划的方法

当前节点A[k],如果满足两种情况之一(从左往右节点依次为k-2,k-1,k)

  1. A[k] > A[k-1],且A[k-2] > A[k-1]

  2. A[k] < A[k-1],且A[k-2] < A[k-1]

    1554041243683

那么状态转移方程为:

dp[i] = dp[i-1] + 1

如果出现了:

  1. A[k-2] > A[k-1] > A[k]

    1554041252783

  2. A[k-2] < A[k-1] < A[k]

这两种情况可以归纳成:A[k] != A[k-1]

那么状态转移方程为:

dp[i] = 2

python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def maxTurbulenceSize(self, A: List[int]) -> int:
n = len(A)
if n == 1:
return 1
dp = [0]*n
if A[0] == A[1]:
dp[0] = 1
dp[1] = 1
else:
dp[0] = 1
dp[1] = 2

for k in range(2,n):
if A[k] > A[k-1] and A[k-2] > A[k-1] or A[k] < A[k-1] and A[k-2] < A[k-1]:
dp[k] = dp[k-1] + 1
elif A[k] != A[k-1]:
dp[k] = 2
return max(dp)
CATALOG
  1. 1. 题目描述
  2. 2. 思路
  3. 3. python代码