使用二分搜索的有效山数组

Question

我正在尝试使用二分搜索解决 leetcode 中有效的山数组问题，但所有测试用例都没有通过这种方法。谁能帮我解决这个问题吗？

class Solution {
    public boolean validMountainArray(int[] arr) {
        int start = 0;
        int end = arr.length - 1;
        int mid = -1;
        while (start < end) {
            mid = start + (end - start) / 2;
            if (arr[mid] > arr[mid+1] && arr[mid] > arr[start] && arr[mid] > arr[end]) {
                return true;
            } else if (arr[mid] > arr[mid + 1]) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return false;

    }
}

我期待所有测试用例都通过

Answer 1

您无法对检查特定索引是否为山峰的函数进行二分搜索，因为它不是单调的。相反，您可以通过数组上的线性循环来验证条件。到达第一个山高比前一个降低的点后，它就再也不会增加了。

示例实现：

public boolean validMountainArray(int[] arr) {
    boolean down = false;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] == arr[i - 1]) return false;
        // strictly increasing/decreasing must have no equal elements
        if (arr[i - 1] > arr[i]) {
            if (i == 1) return false; // has not starting increasing yet
            down = true; // mark as started decreasing
        } else if (down) return false;
        // increasing again after already starting decreasing
    }
    return down; // must have decreasing segment at the end
}