牛客网高频算法题系列-BM19-寻找峰值

题目描述

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

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

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

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

4. 你可以使用O(logN)的时间复杂度实现此问题吗？

原题目见：寻找峰值

解法一：数组遍历

首先，判断几种特殊场景：

• 如果数组为空，则不存在峰值；

• 如果数组只有一个元素，因为都是负无穷，所以第一个元素即为峰值；

• 如果数组的第一个元素比第二个元素大，加上左边负无穷，则第一个元素必为峰值；

• 如果数组的最后一个元素比倒数二个元素大，加上右边边负无穷，则倒数第一个元素必为峰值。

如果不存在以上特殊情况，则从数组的第二位开始遍历数组，判断是否是峰值。

解法一：二分法

原理：因为左右都是负无穷，对于中间的元素，如果nums[mid] > nums[mid + 1]，也就是mid部分递减，加上左边负无穷，所以mid的左边一定会有峰值；同理，如果nums[mid] < nums[mid + 1]，加上右边负无穷，所以mid的右边一定会有峰值。

代码

1.01^{365} ≈ 37.7834343329   

0.99^{365} ≈ 0.02551796445   

相信坚持的力量！