BM19 寻找峰值

目录

描述

示例1

思路

代码

---

描述

给定一个长度为n的数组nums请你找到峰值并返回其索引。数组可能包含多个峰值在这种情况下返回任何一个所在位置即可。
 

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] = −∞−∞

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

数据范围

1≤nums.length≤2×105

如输入[2,4,1,2,7,8,4]时会形成两个山峰一个是索引为1峰值为4的山峰另一个是索引为5峰值为8的山峰如下图所示

示例1

输入[2,4,1,2,7,8,4]

返回值1

说明4和8都是峰值元素返回4的索引1或者8的索引5都可以

思路

通过这个题就要记住要把题好好读一遍首先题目中已经说了边界值为负无穷然后就是相邻的值不能相同要不然这个题看完答案你也懵逼中

有了上面两个条件就可以使用二分法来查询是否有波峰先从中间值来如果左边高左边必有峰如果右边高右边必有峰否则这个索引就是峰

代码

public int findPeakElement (int[] nums) {
        // write code here
        int len = nums.length;
        if (len == 1) {
            return 0;
        }
        int left = 0;
        int right = len - 1;

        return find(nums, left, right);
    }

    private int find(int[] nums, int left, int right) {

        if (left == right) {
            return left;
        }

        int mid = (left + right) / 2;

        if (nums[mid] < nums[mid + 1]) {
            // 右边高肯定有
            return find(nums, mid + 1, right);
        } else if (mid - 1 >= 0 && nums[mid] < nums[mid - 1]) {
            // 左边高肯定有
            return find(nums, left, mid);
        } else {
            return mid;
        }
    }

有一点要注意就是判断右节点是否大的时候有可能-1会变为负数需要判断一下