LeetCode 941. 有效的山脉数组

题目

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：

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

  • arr[0] < arr[1] < ... arr[i-1] < arr[i]
    -arr[i] > arr[i+1] > ... > arr[arr.length - 1]

    
    

例：
输入：arr = [2,1]
输出：false

方法一：暴力解法

• 根据山脉数组的定义，数组长度小于三的一定不是
• 计算数组 arr 的最大值出现的位置 maxIndex
• 根据山脉数组的定义，数组元素应先进行单调递增后进行单调递减，所以最大值位置 maxIndex 一定不位于数组的首尾。分别对数组首部到最大值出现位置 maxIndex 和最大值出现位置 maxIndex 到数组尾部的元素们进行判断，是否符合单调递增/递减，若不符合则返回 False
• 若数组对以上条件均符合则为山脉数组

class Solution(object):
    def validMountainArray(self, arr):
        if len(arr) < 3:
            return False
        
        maxIndex = 0
        for i in range(1, len(arr)):
            if arr[i] > arr[i-1]:
                maxIndex = i
        
        if maxIndex == 0 or maxIndex == len(arr)-1:
            return False
        for i in range(maxIndex):
            if arr[i] >= arr[i+1]:
                return False
        for i in range(maxIndex, len(arr)-1):
            if arr[i] <= arr[i+1]:
                return False
        
        return True

方法二：双指针法

• left 表示左指针，初始值为零；right 表示右指针，初始值为数组 arr 尾部 len(arr)-1
• left 向右移动直至找到某个值，该值大于或等于下一步移动后的值 arr[left+1]，即此时 left 指针指向山峰或多个山峰中的一个
• right 向左移动直至找到某个值，该值大于或等于下一步移动后的值 arr[right-1]，即此时 right 指针指向山峰或多个山峰中的一个
• 判断，根据山脉数组的定义，若两个指针指向同一位置，即只有一个山峰，同时 left 指针不指向数组尾部，right 指针不指向数组首部，即非单调递增/递减，那么为山脉数组

class Solution(object):
    def validMountainArray(self, arr):
        left, right = 0, len(arr)-1
        while left < len(arr)-1 and arr[left+1] > arr[left]:
            left += 1
        while right > 0 and arr[right-1] > arr[right]:
            right -= 1
        if left == right and left != len(arr)-1 and right != 0:
            return True
        else:
            return False

参考

代码相关：https://programmercarl.com/0941.%E6%9C%89%E6%95%88%E7%9A%84%E5%B1%B1%E8%84%89%E6%95%B0%E7%BB%84.html