有效山脉数组

512 次访问 2020-11-12

Walker

给定一个整数数组 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

自我解答

题意很简单，先升到顶然后一路降下来，这里只能转折一次, 因此，可以设置几个
变量记录状态，遍历一遍数组就可以了,

class Solution:
    def validMountainArray(self, A: List[int]) -> bool:
        if len(A) < 3 or A[1] <= A[0]:
            return False
        last, status, turn = A[1], 1, True
        for a in A[2:]:
            if a == last:
                return False
            if (a - last) * status < 0:
                if turn:
                    status = -1
                    turn = False
                else:
                    return False
            last = a
        return not turn

题解

题解使用是双指针，因为这也是个“准有序”的数组了，使用双指针很好地简化了问题

class Solution2:
    def validMountainArray(self, A: List[int]) -> bool:
        length = len(A)
        if length < 3 or A[1] <= A[0] or A[length - 2] <= A[length - 1]:
            return False
        i, j = 1, length - 2
        while i <= length - 2 and A[i] < A[i + 1]:
            i += 1
        while j >= 1 and A[j - 1] > A[j]:
            j -= 1
        return i == j

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