「每日LeetCode」2020年11月3日

本文最后更新于：2023年3月19日 晚上

Lt941. 有效的山脉数组

941. 有效的山脉数组

难度简单 63
给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。
让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

  • A.length >= 3
  • 在 0 < i < A.length - 1 条件下，存在 i 使得：
    • A[0] < A[1] < ... A[i-1] < A[i]
    • A[i] > A[i+1] > ... > A[A.length - 1]

示例 1：

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

示例 2：

1
2
输入：[3,5,5]
输出：false

示例 3：

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

提示：

  1. 0 <= A.length <= 10000
  2. 0 <= A[i] <= 10000

思路

上坡下坡计数（状态记录）

使用一个 count 记录上坡下坡状态，为 1 时则为上坡，为 2 时则为下坡：

  1. 可能直接开始下坡，所以要先判断第一二个元素是否上坡。
  2. 遍历元素，当下一个元素小于当前元素时，count++，开始下坡。
  3. 如果下一个元素大于等于当前元素，说明出现上坡或平地，返回 false。
  4. 遍历后如果 count 不等于 2，说明没有出现下坡，返回 false。

遍历

找到最高峰，判断是否是数组最后一位，是的话返回 false。
两侧开始往下判断是否都是下坡，不是的话返回 false。

解答

上坡下坡计数（状态记录）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} A
 * @return {boolean}
 */
var validMountainArray = function (A) {
  let count = 0;
  if (A[0] < A[1]) count++;
  else return false;
  for (let i = 0; i < A.length - 1; i++) {
    if (count === 1) {
      if (A[i + 1] < A[i]) count++;
    } else if (count === 2) {
      if (A[i + 1] >= A[i]) return false;
    }
  }
  if (count === 2) return true;
  return false;
};

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} A
 * @return {boolean}
 */
var validMountainArray = function (A) {
  let maxIndex = 0;
  for (let i = 0; i < A.length; i++)
    maxIndex = A[maxIndex] > A[i] ? maxIndex : i;
  if (maxIndex === 0 || maxIndex === A.length - 1) return false;
  let p = maxIndex;
  while (p > 0) {
    if (A[p - 1] >= A[p]) return false;
    p--;
  }
  p = maxIndex;
  while (p < A.length) {
    if (A[p + 1] >= A[p]) return false;
    p++;
  }
  return true;
};