leetCode ✏Leetcode基础刷题之(162. Find Peak Element)
✏描述
求给定数组中局部最大峰值，返回其下标，局部最大峰值也就是比左右两边的数都大。
✏题目实例
✏题目分析
看第一版最简单的。直接遍历，存在返回，一目了然。如果后一个值比当前值小，那么说明当前值就是一个峰值，否则继续下一个比较，是一个递增的比较
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function findPeakElement($nums) {
for($i=0;$i < count($nums)-1;$i++){
if($nums[$i] >$nums[$i+1]) return $i;
}
return count($nums)-1;
}
题目要求我们在O(nlogn)时间复杂度中完成，那么上面显然不行。可以使用二分查找的思想，取得中间数之后，和后一个数进行比较，如果大于后一个数，说明局部最大峰值在中间数之前，如果小于，说明局部最大峰值在中间数之后。为了提高效率，这里的使用了位运算来获取中间值。
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function findPeakElement($nums) {
$l=0;
$r=count($nums)-1;
while($l<$r)
$middle=$l+(($r-$l)>>1);
if($nums[$middle]>$nums[$middle+1]){
$r=$middle;
}else{
$l=$middle+1;
}
}
return $l;
}
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)