【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]

遍历

class Solution {
    public boolean validMountainArray(int[] arr) {
        int n = arr.length;
        int index = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[index]) index = i;
        }
        if (index == 0 || index == n - 1) return false;
        for (int i = 1; i <= index; i++) {
            if (arr[i - 1] >= arr[i]) return false;
        }
        for (int i = index; i < n - 1; i++) {
            if (arr[i] <= arr[i + 1]) return false;
        }
        return true;
    }
}

• 先排序找到最大的元素下标位置，然后比较index左边和右边是否符合山脉数组的要求

双指针

class Solution {
    public boolean validMountainArray(int[] arr) {
        int l = 0, r = arr.length - 1;
        // 注意防止指针越界
        while (l + 1 < arr.length && arr[l] < arr[l + 1]) {
            l++;
        }
        // 注意防止指针越界
        while (r > 0 && arr[r] < arr[r - 1]) {
            r--;
        }
        // 如果l或者r都在起始位置，说明不是山峰
        return l == r && l != 0 && r != arr.length - 1;
    }
}

• 如果left或者right没有移动，说明是一个单调递增或者递减的数组，依然不是山峰