🌗 941. 有效的山脉数组

难度: 🌗

问题描述

---

解法 1 - 单向线性查找

class Solution {
    public boolean validMountainArray(int[] arr) {
        // 思路：
        int len = arr.length;
        // 特殊情况特判
        if(len < 3) {
            return false;
        }
        int i = 0;
        while(i < len - 1) {
            if(arr[i + 1] > arr[i]) {
                i ++;
            } else if(arr[i + 1] == arr[i]) {
                return false;
            } else {
                break; // arr[i + 1] < arr[i]
            }
        }
        // System.out.println(i);
        if(i == 0 || i >= len - 1) {
            return false;
        }
        // i < len - 1
        while(i < len - 1) {
            if(arr[i] > arr[i + 1]) {
                i ++;
            } else {
                // System.out.println(i);
                return false;
            }
        }
        return true;
    }
}

---

输出 1

---

解法 2 - 双指针

class Solution {
    public boolean validMountainArray(int[] arr) {
        // 思路：
        // 双指针
        // 两边往中间查找，分别寻找符合条件的峰顶，判断是否为同一个峰顶
        int len = arr.length;
        int left = 0;
        int right = len - 1;
        for(int i = 0; i < len - 1; i ++) {
            if(arr[i + 1] == arr[i]) {
                return false; // 不能出现相同的值
            } else if(arr[i + 1] < arr[i]) {
                left = i; // 找到左侧峰顶
                break;
            }
        }
        if(left == 0 || left == len - 1) {
            return false;
        }
        for(int j = len - 1; j > 0; j --) {
            if(arr[j - 1] == arr[j]) {
                return false;
            } else if(arr[j - 1] < arr[j]) {
                right = j;
                break;
            }
        }
        return left == right;
    }
}

---

输出 2