问题描述

给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

• A.length >= 3
• 在 0 < i < A.length - 1 条件下，存在 i 使得：
  • A[0] < A[1] < ... A[i-1] < A[i]
  • A[i] > A[i+1] > ... > A[A.length - 1]

示例 1：

输入：[2,1]
输出：false

示例 2：

输入：[3,5,5]
输出：false

示例 3：

输入：[0,3,2,1]
输出：true

提示：

• 0 <= A.length <= 10000
• 0 <= A[i] <= 10000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/valid-mountain-array

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

设置变量：

• state 表示处于上升状态（0），还是下降状态（1），初值为 0
• left 表示山顶左面的长度，初值为 0
• right 表示山顶右面的长度，初值为 0

从第 2 个元素开始，将每个元素与它前面的元素比较：

• 如果它大于前面的元素，并且 state 等于 0，那么说明正在上升，将 left 增加 1；如果 state 等于 1，那么说明在下降阶段，遇到了上升的情形，返回 false
• 如果它等于前面的元素，那么返回 false
• 否则如果state 等于 0，那么说明前面的元素是山顶，将 state 置为 1，从此时起进入到下降阶段；如果 state 等于 1，那么说明正在下降。然后将 right 增加 1

最终，如果 left 和 right 都大于 0，则说明数组是有效的山脉数组

Python 实现

class Solution(object):
    def validMountainArray(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        if A is None or len(A) < 3:
            return False

        ind = 1
        state = 0
        left = 0
        right = 0
        while ind < len(A):
            if A[ind] == A[ind - 1]:
                return False
            elif A[ind] > A[ind - 1]:
                if state == 1:
                    return False
                left = left + 1
            else:
                if state == 0:
                    state = 1
                right = right + 1
            ind = ind + 1
        return left > 0 and right > 0