?？途W(wǎng)高頻算法題系列-BM19-尋找峰值
題目描述
給定一個(gè)長度為n的數(shù)組nums，請你找到峰值并返回其索引。數(shù)組可能包含多個(gè)峰值，在這種情況下，返回任何一個(gè)所在位置即可。
峰值元素是指其值嚴(yán)格大于左右相鄰值的元素。嚴(yán)格大于即不能有等于
假設(shè) nums[-1] = nums[n] = -\infty?∞
對于所有有效的 i 都有 nums[i] != nums[i + 1]
原題目見：
解法一：數(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)持的力量！
標(biāo)簽：
