leetcode 941. 有效的山脉数组网站首页 其他

leetcode 941. 有效的山脉数组

dengjiayue 2024-06-27 12:01:03

简介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]

示例 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

模拟:

遍历递增,不再递增时退出如果没有或者只有递增返回false,
遍历递减,不再递减时退出
判断当前位置与数组长度是否相等,如果相等返回真否则返回假

时间复杂度(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
}