Leetcode 941. Valid Mountain Array

Tyan

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

2160

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

文章被收录于专栏：SnailTyanSnailTyan

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

1. Description

2. Solution

**解析：**Version 1，通过up和down分别表示山脉的上下过程，比较数组前后两个数，如果相等，直接返回False，如果前者大于后者，没出现过下山down=False，则将上山设为up=True，如果前者小于后者，出现了上山up=False，则将下山设为down=True，不符合上述条件的都直接返回False，最后如果上山下山都出现了，则返回True，否则返回False。Version 2使用双指针分别从左右两侧移动，最后判断两个指针是否满足山脉条件，不满足返回False，满足返回True。

Version 1

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        n = len(arr)
        up = False
        down = False
        for i in range(n - 1):
            if arr[i+1] == arr[i]:
                return False
            elif arr[i+1] > arr[i]:
                up = True
                if down:
                    return False
            else:
                if not up:
                    return False
                down = True
        if up and down:
            return True
        return False

Version 2

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        n = len(arr)
        if n < 3:
            return False
        i = 1
        j = n - 2
        while i < n and arr[i] > arr[i-1]:
            i += 1
        i -= 1
        while j > -1 and arr[j] > arr[j+1]:
            j -= 1
        j += 1
        if i == 0 or j == n - 1 or i != j:
            return False
        return True