标签: 数组
难度: Easy
给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。
让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：
arr.length >= 30 < i < arr.length - 1 条件下，存在 i 使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i] arr[i] > arr[i+1] > ... > arr[arr.length - 1]
示例 1：
输入：arr = [2,1] 输出：false
示例 2：
输入：arr = [3,5,5] 输出：false
示例 3：
输入：arr = [0,3,2,1] 输出：true
提示：
1 <= arr.length <= 1040 <= arr[i] <= 104运行时间: 26 ms
内存: 17.0 MB
class Solution:
def validMountainArray(self, arr: List[int]) -> bool:
if len(arr)<3 or arr[1]<=arr[0] or arr[-1]>=arr[-2]:
return False
peak = False
pre = arr[0]
for num in arr[1:]:
if num==pre:
return False
if not peak and num<pre:
peak = True
elif peak and num>pre:
return False
pre = num
return True
解题思路是模拟爬山的过程。首先检查数组长度是否小于3，或者数组的第二个元素小于等于第一个元素，或者数组的最后一个元素大于等于倒数第二个元素的情况，这些情况都直接返回false。然后使用一个变量peak来标记是否已经达到山顶。遍历数组，如果当前元素等于前一个元素，返回false，因为山脉数组中元素必须严格递增或递减。如果未达到山顶且当前元素小于前一个元素，则标记已达到山顶。如果已达到山顶但当前元素大于前一个元素，则返回false。如果成功遍历完成，则返回true。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def validMountainArray(self, arr: List[int]) -> bool:
# 如果数组长度小于3，或者头尾元素不符合山脉的特性，则直接返回False
if len(arr)<3 or arr[1]<=arr[0] or arr[-1]>=arr[-2]:
return False
peak = False # 初始化未到达山顶
pre = arr[0] # 初始化前一个元素
for num in arr[1:]: # 遍历数组中除了第一个元素外的其他元素
if num==pre: # 如果当前元素等于前一个元素，则不是山脉数组
return False
if not peak and num<pre: # 如果还未到达山顶且当前元素小于前一个元素
peak = True # 标记已到达山顶
elif peak and num>pre: # 如果已到达山顶但当前元素大于前一个元素
return False
pre = num # 更新前一个元素为当前元素
return True # 成功遍历整个数组，返回True
这两个条件用于确保数组可以形成一个山脉的形状。`arr[1] <= arr[0]`条件排除了数组开头是下坡或平坦的情况，因为一个有效的山脉数组必须从低处开始上升。相似地，`arr[-1] >= arr[-2]`条件排除了数组结尾是上升或平坦的情况，确保山脉在达到顶峰后必须下降。这两个条件是为了确保数组开始时上升并在结束前下降，符合山脉的基本形态。
代码中，`peak`变量在初始设置为`False`，表示山顶未被到达。当检测到第一次元素从上升转为下降时（即`num < pre`），`peak`会被设置为`True`，代表已经到达山顶。此后，`peak`不会被重新设置，这确保了山顶只被标记一次。如果数组中存在多个上升后再下降的序列，即存在多个峰值，那么在第二次尝试上升（即遇到`num > pre`且`peak`已为`True`）时，代码将返回`False`，因为有效的山脉数组中只能有一个顶峰。
代码的逻辑确实考虑了只有单段递减的情况。在`peak`被设置为`True`后，任何后续的上升（`num > pre`）都会触发函数返回`False`。这意味着，如果存在多段递减序列（即在下降后再次上升再下降），代码将正确地判断这不是一个有效的山脉数组。因此，一旦开始下降，再次上升将被视为不符合山脉数组的条件。
在该算法中，一旦`peak`被设置（即已经到达山顶并开始下降），任何后续的`num > pre`（即再次上升）都会导致返回`False`。这种设计是基于题目要求，即山脉数组在到达峰顶后必须严格递减，不存在再次上升的情况。因此，这里没有考虑输入误差或特殊情况，如微小的波动或数据错误，算法严格遵守题目的定义。