题解 |【清晰图解】 #二叉树中和为某一值的路径(一)#用“爬山”彻底秒杀

默认你已经理解题意了哈

1 思路如下

首先要注意题目说的条件，在题目描述里面出现了 nums[-1] = nums[n] = -∞，代表什么？代表着只要数组中存在一个元素比相邻元素大，那么沿着它就一定能找到一个峰值

根据上述结论，我们就可以使用二分查找来找到峰值

查找的时侯，左指针 l，右指针 r，让它们保持左右顺序为循环条件

然后根据左右指针去算中间位置 m，并比较 m 与 m+1 的值那个大，如果 m 较大，说明左侧存在峰值，r = m，如果 m + 1 较大，说明右侧是存在峰值，l = m + 1

可能上面图解思路你可能还是很懵逼，我这里通俗解释下啥意思，这道题，我觉得最最最重要的是条件，两边都是负无穷的时候，数组当中可能有很多个波峰，也可能只有一个，其实我们尝试画图，跟股票信息一毛一样，没有规律啊，如果根据中点値判断我们的二分方向该往哪里走， 这道题要求我们只返回一个波峰。你这样想啊，中点所在地方，可能是某座山的山峰，山的下坡处，山的上坡处，那如果是山峰呢，最终二分终止也会找到，关键是我们的二分方向往那边走，现在并不知道山峰在我们左边还是右边，送你两个字你就恍然大悟，爬山（没错，带你去爬山（张东升附体）），那如果你往下坡方向走，也许遇到新的山峰，但是也许是一个一直下降的坡啊，然后到边界。但是如果你往上坡方向走的话，就算你最后一直上的边界，由于最边界那是负无穷，所以你就一定能找到山峰，好吧说了这么多总结的一句话，往递增的方向上，二分，它是一定能找到的，但是往递减的方向只是可能找到，也许根本找不到的哈

2 写下代码

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        for (; left < right; ) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

3 时间复杂度

• 是O(logN)级别