题目描述

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]

示例 1：

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

输入：arr = [3,5,5] 输出：false 示例 3：

输入：arr = [0,3,2,1] 输出：true

提示：

1 <= arr.length <= 104 0 <= arr[i] <= 104

解题思路

法1

模拟:

1. 遍历递增,不再递增时退出如果没有或者只有递增返回false,

2. 遍历递减,不再递减时退出

3. 判断当前位置与数组长度是否相等,如果相等返回真否则返回假

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

首先，我们从数组的开头开始递增扫描，直到找到最高点（arr[i] > arr[i+1]）。

然后，我们检查最高点不能是数组的第一个或最后一个元素，如果满足条件，则继续进行递减扫描，直到数组的末尾。

最后，检查是否已经扫描到了数组的最后一个元素，如果是，则表示是有效的山脉数组，返回true，否则返回false。

func validMountainArray(arr []int) bool {
    n := len(arr)
    if n < 3 {
        return false
    }

    i := 0

    // 递增扫描
    for i+1 < n && arr[i] < arr[i+1] {
        i++
    }

    // 最高点不能是数组的第一个或最后一个元素
    if i == 0 || i == n-1 {
        return false
    }

    // 递减扫描
    for i+1 < n && arr[i] > arr[i+1] {
        i++
    }

    // 最后一个元素必须小于第一个递增序列的元素
    return i == n-1
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 24 ms , 在所有 Go 提交中击败了 41.30% 的用户 内存消耗： 6.3 MB , 在所有 Go 提交中击败了 68.84% 的用户 通过测试用例： 53 / 53 炫耀一下:

法2

法3