941. 有效的山脉数组

题目描述

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

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

题解

方法一?【暴力破解】【分治算法】

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        l = len(arr)
        if l < 3:
            return False
        index_max = arr.index(max(arr))
        if arr.count(max(arr)) > 1 or index_max==0 or index_max==l-1:
            return False
        for i in range(index_max):
            if arr[i] >= arr[i+1]:
                return False
        for i in range(index_max,l-1):
            if arr[i] <= arr[i+1]:
                return False

        return True

方法二?【双指针】

// 因为当n==2时，n=1的情况已经被计算；n==1时需要返回的时n=0的情况，所以边界条件为n==1
class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        l = len(arr)
        if l < 3:
            return False
        begin = 0
        end = l - 1
        while arr[begin] < arr[begin+1] and begin < l-2:
            begin += 1
        while arr[end] < arr[end-1] and end > 0:
            end -= 1
        if begin != end or begin == 0 or end == l - 1:
            return False
        return True

方法三?【动态规划】

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        l = len(arr)
        if l < 3:
            return False
        dp_left = [1 for _ in range(l)]
        dp_right = [1 for _ in range(l)]
        for i in range(1, l-1):
            if arr[i] > arr[i-1]:
                dp_left[i] = dp_left[i-1] + 1
        for i in range(l-2,-1,-1):
            if arr[i] > arr[i+1]:
                dp_right[i] = dp_right[i+1] + 1
        left_max = max(dp_left)
        right_max = max(dp_right)
        if left_max == 1 or right_max == 1:
            return False
        return (left_max+right_max) == l+1

941. 有效的山脉数组

原文：https://www.cnblogs.com/bladers/p/14266989.html