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+1] > … > arr[arr.length - 1]

示例 1:

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

示例 2:

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

提示:

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

解析

使用双指针从两端向中间遍历，找到山峰位置，判断是否满足山脉数组的条件。

var validMountainArray = function (arr) {
  const n = arr.length;
  if (n < 3) return false;

  let left = 0;
  while (left + 1 < n && arr[left] < arr[left + 1]) {
    left++;
  }

  if (left === 0 || left === n - 1) return false;

  while (left + 1 < n && arr[left] > arr[left + 1]) {
    left++;
  }

  return left === n - 1;
};

时间复杂度 O(n)，空间复杂度 O(1)。