Leetcode 978. Longest Turbulent Subarray

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Longest Turbulent Subarray

2. Solution

解析:Version 1,根据题意,数字的大小关系一直在反转,因此这里采用一个布尔值来表示下一个比较状态,每次比较后都将布尔值反转,只要比较状态和布尔值相等,则动荡序列的长度加1。由于初始布尔值状态未知,因此设为None。当前数字与下一个数字相等时,布尔值设为None,计数器设为1。依次比较数字时,首先排除数字相等的状态,前后两个数字相等时,以下一个数字作为初始序列数字,重新计数。当数字比较顺序与布尔值不相等时,则对当前两个数字的比较状态取反作为下一次比较的状态,且当前两个数字应该作为初始序列长度,因此count=2,布尔值不更新。Version 2是动态规划,Version 3是另一种形式的动态规划。

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
n = len(arr)
maximum = 1
count = 0
flag = None
for i in range(n-1):
if arr[i] == arr[i+1]:
count = 1
flag = None
continue
if flag is None:
flag = not (arr[i] > arr[i+1])
count = 2
else:
if (arr[i] > arr[i+1]) == flag:
count += 1
flag = not flag
else:
# flag = not (arr[i] > arr[i+1])
count = 2
maximum = max(maximum, count)
return maximum
  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
n = len(arr)
high = [1] * n
low = [1] * n
for i in range(n-1):
if arr[i] > arr[i+1]:
high[i+1] = low[i] + 1
elif arr[i] < arr[i+1]:
low[i+1] = high[i] + 1
maximum = max(max(high), max(low))
return maximum
  • Version 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
n = len(arr)
maximum = 1
high = 1
low = 1
for i in range(n-1):
if arr[i] > arr[i+1]:
high = low + 1
low = 1
elif arr[i] < arr[i+1]:
low = high + 1
high = 1
else:
high = 1
low = 1
maximum = max(maximum, max(high, low))
return maximum

Reference

  1. https://leetcode.com/problems/longest-turbulent-subarray/
如果有收获,可以请我喝杯咖啡!