Leetcode 978. Longest Turbulent Subarray

Tyan

发布于 2021-07-29 16:01:09

2320

文章被收录于专栏：SnailTyanSnailTyan

1. Description

2. Solution

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

Version 1

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

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

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

https://leetcode.com/problems/longest-turbulent-subarray/

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/07/27 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度

Leetcode 978. Longest Turbulent Subarray

Leetcode 978. Longest Turbulent Subarray

1. Description

2. Solution

Reference

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐