题目描述

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。

有效山脉数组的定义：

  • arr.length >= 3
  • 存在某个下标 i（0 < i < arr.length - 1）使得：
    • arr[0] < arr[1] < ... < arr[i-1] < arr[i]
    • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

即数组先严格递增，到某个峰值后严格递减。峰值不能在数组的首尾位置。

例如：

  • arr = [0,3,2,1] → true（峰值 3 在下标 1）
  • arr = [3,5,5] → false（有相等元素，不是严格递增/递减）
  • arr = [0,1,2,3] → false（只有递增，没有递减）

解题思路

本题可以用线性扫描（类似双指针的思想）一次遍历解决。

算法步骤

  1. 如果数组长度小于 3，直接返回 false（不满足山峰的最短长度要求）。

  2. 第一阶段：爬坡（递增段扫描）

    • 从下标 0 开始向右遍历，只要 arr[i] < arr[i+1] 就继续向前。
    • 当不再满足严格递增时停下，此时 i 即为候选峰值位置。

  3. 第二阶段：下坡（递减段扫描）

    • 从峰值位置 i 继续向右遍历，只要 arr[j] > arr[j+1] 就继续向前。
    • 如果在这个过程中发现 arr[j] <= arr[j+1]（即不满足严格递减），说明不是山峰，直接返回 false。

  4. 边界检查：

    • 峰值位置 i 不能是 0（说明数组一开始就在递减，没有上升段）。
    • 峰值位置 i 不能是 arr.length - 1（说明数组从头到尾都在递增，没有下降段）。

  5. 如果以上全部通过，返回 true。

为什么这是正确的？

山脉数组要求恰好一个峰值，峰值左侧严格递增、右侧严格递减。我们通过一次线性扫描依次验证这两个单调性质，并在最后检查峰值是否在有效位置（不在两端），即可完全判定。

这种”先找坡度变化点，再验证两侧”的方法等价于使用两个指针分别从两侧向中间爬坡的经典解法，但只需一次遍历，更为简洁。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组长度。每个元素至多被访问一次。
  • 空间复杂度：O(1)，只使用了常数级别的额外空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package code.J941;

public class J941 {
    public boolean validMountainArray(int[] arr) {
        if (arr.length < 2) return false;
        int i = 0;
        for (; i < arr.length - 1; i++) {
            if (arr[i] >= arr[i + 1]) break;
        }
        for (int j = i; j < arr.length - 1; j++) {
            if (arr[j] <= arr[j + 1]) return false;
        }
        return i != 0 && i != arr.length - 1;
    }
}