LeetCode 941 有效的山脉数组 题解

• 常规方法：线性扫描
• 双指针，从两边找山峰

LeetCode链接

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。
让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：
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]

示例 1：
输入：arr = [2,1]
输出：false
示例 2：
输入：arr = [3,5,5]
输出：false
示例 3：
输入：arr = [0,3,2,1]
输出：true
提示：
1 <= arr.length <= 104
0 <= arr[i] <= 104

常规方法：线性扫描

时间复杂度：O(N)，其中 N 是数组 A 的长度。
空间复杂度：O(1)。

class Solution {
    public boolean validMountainArray(int[] A) {
        if(A == null || A.length < 2){
            return false;
        }
        //开头就不符合要求
        if(A[1] <= A[0]){
            return false;
        }
        int length = A.length;
        int i = 1;
        //先找山顶
        while((i<length)&&(A[i]>A[i-1])){
            i++;
        }
        //山顶不能是最后一个元素
        if(i==length){
            return false;
        }
        //再找山谷，如果有相等的情况也会跳出来
        while((i<length)&&(A[i]<A[i-1])){
            ++i;
        }
        //看山谷是否在最后
        return i==length;
    }
}

双指针，从两边找山峰

class Solution {
    public boolean validMountainArray(int[] A) {
        if(A == null || A.length < 2){
            return false;
        }
        int length = A.length;
        int head = 0,tail = A.length-1;
        while((head+1) < A.length && A[head+1]>A[head]){
            head++;
        }
        while((tail-1)>0 && A[tail-1] > A[tail]){
            tail--;
        }
        //从左边和从右边找到的两个山峰应该相同，并且不是在边上
        return head == tail && head > 0 && tail<length-1;
    }
}