TNotes.leetcode

Appearance

0941. 有效的山脉数组【简单】

0941. 有效的山脉数组【简单】 ​

1. 📝 题目描述 ​

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

img

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^4

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * @param {number[]} arr
 * @return {boolean}
 */
var validMountainArray = function (arr) {
  const n = arr.length

  // 长度小于 3 不可能是山脉数组
  if (n < 3) return false

  let i = 0

  // 上坡：找到递增序列的终点
  while (i < n - 1 && arr[i] < arr[i + 1]) {
    i++
  }

  // 峰顶不能在数组开始或结束位置
  if (i === 0 || i === n - 1) return false

  // 下坡：检查剩余部分是否严格递减
  while (i < n - 1 && arr[i] > arr[i + 1]) {
    i++
  }

  // 如果遍历完整个数组，说明是有效的山脉数组
  return i === n - 1
}
  • 时间复杂度：O(n)，最多遍历数组 1 次
  • 空间复杂度：O(1)，只使用了常数级别的额外空间

Discussions