牛客網(wǎng)高頻算法題系列-BM19-尋找峰值

題目描述

給定一個(gè)長度為n的數(shù)組nums，請你找到峰值并返回其索引。數(shù)組可能包含多個(gè)峰值，在這種情況下，返回任何一個(gè)所在位置即可。

1. 峰值元素是指其值嚴(yán)格大于左右相鄰值的元素。嚴(yán)格大于即不能有等于

2. 假設(shè) nums[-1] = nums[n] = -\infty?∞

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

4. 你可以使用O(logN)的時(shí)間復(fù)雜度實(shí)現(xiàn)此問題嗎？

原題目見：尋找峰值

解法一：數(shù)組遍歷

首先，判斷幾種特殊場景：

• 如果數(shù)組為空，則不存在峰值；

• 如果數(shù)組只有一個(gè)元素，因?yàn)槎际秦?fù)無窮，所以第一個(gè)元素即為峰值；

• 如果數(shù)組的第一個(gè)元素比第二個(gè)元素大，加上左邊負(fù)無窮，則第一個(gè)元素必為峰值；

• 如果數(shù)組的最后一個(gè)元素比倒數(shù)二個(gè)元素大，加上右邊邊負(fù)無窮，則倒數(shù)第一個(gè)元素必為峰值。

如果不存在以上特殊情況，則從數(shù)組的第二位開始遍歷數(shù)組，判斷是否是峰值。

解法一：二分法

原理：因?yàn)樽笥叶际秦?fù)無窮，對于中間的元素，如果nums[mid] > nums[mid + 1]，也就是mid部分遞減，加上左邊負(fù)無窮，所以mid的左邊一定會(huì)有峰值；同理，如果nums[mid] < nums[mid + 1]，加上右邊負(fù)無窮，所以mid的右邊一定會(huì)有峰值。

代碼

1.01^{365} ≈ 37.7834343329 ??

0.99^{365} ≈ 0.02551796445 ??

相信堅(jiān)持的力量！