Leetcode 941. Valid Mountain Array

逃离我推掉我的手 2022-09-09 00:12 113阅读 0赞

文章作者：Tyan  
博客：[noahsnail.com][] | [CSDN][] | [简书][Link 1]

## 1. Description ##

![Valid Mountain Array][]

## 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

## Reference ##

1.  [https://leetcode.com/problems/valid-mountain-array/][https_leetcode.com_problems_valid-mountain-array]

[noahsnail.com]: http://noahsnail.com
[CSDN]: http://blog.csdn.net/quincuntial
[Link 1]: http://www.jianshu.com/users/7731e83f3a4e/latest_articles
[Valid Mountain Array]: /images/20220829/e18f422982014d6da0c9a74a22d46ccf.png
[https_leetcode.com_problems_valid-mountain-array]: https://leetcode.com/problems/valid-mountain-array/