leetcode941(有效的山脉数组)–Java语言实现

求：

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

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

输入：[3,5,5]
输出：false
示例 3：

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

提示：

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

题目链接： https://leetcode-cn.com/problems/valid-mountain-array/

解：

线性扫描

根据题目要求，如果数组元素少于3个，直接返回false。在数组元素大于等于3个的前提下，数组应该先严格单调递增，再严格单调递减。使用一个变量i记录当前的索引。第一个while循环，当元素是单调增时，自增i。如果退出第一个while循环时，发现i==0，说明没有出现过单调增。如果退出第一个while循环时，发现i==A.length-1，说明整个数组都是单调增。这俩种情况应该返回false。

在第二个循环中，判断元素是否均为单调减，如果元素均为单调减，i在退出时的值应该为A.length-1。通过判断i是否与A.length-1相等，即可判断是否是山脉数组。

时间复杂度：O(N)

空间复杂度：O(1)

public boolean validMountainArray(int[] A) {
    if (A.length < 3) return false;
    int i = 0;
    while (i < A.length - 1 && A[i] < A[i + 1]) ++i;
    if (i == 0 || i == A.length - 1) return false;
    while (i < A.length - 1 && A[i] > A[i + 1]) ++i;
    return i == A.length - 1;
}