有效的山脉数组 力扣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] > 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

二、思路

        第一时间想到的是先找到数字的最大值的下标也就是山峰的位置，再分别判断左半和右半是否是严格递增和递减的。不过要注意数组单调的话也不是山脉数组。

        然后再想有没有别的方法更高效，看了大佬的思路发现可以用相向指针解决。

三、代码

遍历法：

class Solution {
    public boolean validMountainArray(int[] arr) {
        if(arr.length < 3) {
            return false;
        }
        //先找到数字的最大值的下标也就是山峰的位置
        int max = 0;
        int index = 0;
        for(int i = 0;i< arr.length;i++) {
            if(arr[i] > max) {
                max = arr[i];
                index = i;
            }
        }
        //单调的话也不是山峰
        if(index == arr.length - 1 || index == 0) {
            return false;
        }
        //再分别判断左半和右半是否是严格递增和递减的。
        for(int j = 0;j < index;j++) {
            if(arr[j] >= arr[j+1]) {
                return false;
            }
        }
        for(int j = index;j<arr.length - 1;j++) {
            if(arr[j] <= arr[j+1]) {
                return false;
            }
        }
        return true;
    }
}

双指针法：

class Solution {
    public boolean validMountainArray(int[] arr) {
        if (arr.length < 3) { // 此时，一定不是有效的山脉数组
            return false;
        }
        // 双指针
        int left = 0;
        int right = arr.length - 1;
        // 注意防止指针越界
        while (left + 1 < arr.length && arr[left] < arr[left + 1]) {
            left++;
        }
        // 注意防止指针越界
        while (right > 0 && arr[right] < arr[right - 1]) {
            right--;
        }
        // 如果left或者right都在起始位置，说明不是山峰
        if (left == right && left != 0 && right != arr.length - 1) {
            return true;
        }
        return false;
    }
}