題目
給定一個整數(shù)數(shù)組 arr，如果它是有效的山脈數(shù)組就返回 true执赡，否則返回 false镰踏。讓我們回顧一下，如果 arr 滿足下述條件沙合，那么它是一個山脈數(shù)組：
- 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
方法一：暴力解法
- 根據(jù)山脈數(shù)組的定義，數(shù)組長度小于三的一定不是
- 計算數(shù)組 arr 的最大值出現(xiàn)的位置 maxIndex
- 根據(jù)山脈數(shù)組的定義，數(shù)組元素應先進行單調遞增后進行單調遞減绊率，所以最大值位置 maxIndex 一定不位于數(shù)組的首尾含末。分別對數(shù)組首部到最大值出現(xiàn)位置 maxIndex 和最大值出現(xiàn)位置 maxIndex 到數(shù)組尾部的元素們進行判斷，是否符合單調遞增/遞減即舌，若不符合則返回 False
- 若數(shù)組對以上條件均符合則為山脈數(shù)組
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 表示右指針顽聂，初始值為數(shù)組 arr 尾部 len(arr)-1
- left 向右移動直至找到某個值，該值大于或等于下一步移動后的值 arr[left+1]盯仪，即此時 left 指針指向山峰或多個山峰中的一個
- right 向左移動直至找到某個值紊搪，該值大于或等于下一步移動后的值 arr[right-1]，即此時 right 指針指向山峰或多個山峰中的一個
- 判斷全景，根據(jù)山脈數(shù)組的定義耀石，若兩個指針指向同一位置，即只有一個山峰爸黄，同時 left 指針不指向數(shù)組尾部滞伟，right 指針不指向數(shù)組首部，即非單調遞增/遞減炕贵，那么為山脈數(shù)組
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
