Leetcode 845. Longest Mountain in Array

Tyan

发布于 2021-09-06 15:39:17

2590

发布于 2021-09-06 15:39:17

文章被收录于专栏：SnailTyan SnailTyanSnailTyan

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

1. Description

2. Solution

**解析：**Version 1，统计山脉元素个数，首先山脉是先上后下，up和down的状态分别表示山脉的上下状态，初始状态都为False，只有down=True时，才记录山脉的最大长度，即最大子数组的长度，当后一个元素大于前一元素时，如果up=True，说明已经记录了上坡长度，此时判断下坡是否也记录了，如果down=True，则说明此次上坡是下一山脉的开始，则down=False, count=2，如果down=False，说明还处于当前山脉的上坡阶段，此时count+=1，如果up=False，则说明是山脉的刚开始，此时up=True, count=2；当后一个元素小于前一元素时，如果up=True，说明此时是当前山脉的下坡阶段，count+=1, down=True；如果up=False，说明此时不处于任何山脉的记录阶段，如果两个元素相等，重置up=False, down=False，时间复杂度O(n)。

Version 1

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        maximum = 0
        up = False
        down = False
        for i in range(n - 1):
            if arr[i+1] > arr[i]:
                if up:
                    if down:
                        down = False
                        count = 2
                    else:
                        count += 1
                else:
                    up = True
                    count = 2
            elif arr[i+1] < arr[i]:
                if up:
                    count += 1
                    down = True
            else:
                up = False
                down = False
            if down:
                maximum = max(maximum, count)
        if maximum < 3:
            return 0
        return maximum