使用Binary Search解决LeetCode有效山脉数组问题遇测试用例全失败求协助

你的代码存在几个核心问题，导致无法通过所有测试用例：

• 提前返回逻辑错误：仅判断mid位置是局部峰值就返回true，但没有验证整个数组是否严格遵循「先递增到峰值，再递减」的规则，比如数组[1,3,2,4]会被误判为有效山脉。
• 未处理边界情况：数组长度小于3时，不可能构成山脉数组，你的代码没有做这个判断。
• 峰值位置合法性未验证：峰值不能是数组的第一个或最后一个元素（必须同时有上坡和下坡），你的代码没有检查这一点。
• 未验证全程单调性：即使找到峰值，也需要确保左侧从起点到峰值是严格递增，右侧从峰值到终点是严格递减，原代码跳过了这一步。

修正后的代码 #

class Solution {
    public boolean validMountainArray(int[] arr) {
        // 边界处理：长度不足3直接返回false
        if (arr.length < 3) {
            return false;
        }
        
        int start = 0;
        int end = arr.length - 1;
        
        // 二分查找峰值位置
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (arr[mid] > arr[mid + 1]) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        
        // 峰值不能是第一个或最后一个元素
        if (start == 0 || start == arr.length - 1) {
            return false;
        }
        
        // 验证左侧严格递增
        for (int i = 0; i < start; i++) {
            if (arr[i] >= arr[i + 1]) {
                return false;
            }
        }
        
        // 验证右侧严格递减
        for (int i = start; i < arr.length - 1; i++) {
            if (arr[i] <= arr[i + 1]) {
                return false;
            }
        }
        
        return true;
    }
}

代码说明 #

1. 边界判断：先过滤长度小于3的数组，直接返回false。
2. 二分找峰值：通过二分法找到数组中最大元素的位置（也就是峰值候选），逻辑是：如果mid位置元素大于右侧，说明峰值在左半部分；否则在右半部分。
3. 峰值合法性检查：确保峰值不在数组两端，否则无法形成上坡+下坡的结构。
4. 单调性验证：分别遍历左侧和右侧，确保左侧严格递增、右侧严格递减，这是山脉数组的核心要求。

内容的提问来源于stack exchange，提问作者Avijit Patra