题解 | #寻找峰值#

<?php


/*
- [BM19 寻找峰值](https://www.nowcoder.com/share/jump/4163484761690942105670)
- 时间复杂度  
*/


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
 */
function findPeakElement( $nums )
{
    // write code here
    // 峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
    // 你可以假设 nums[-1] = nums[n] = -∞
    $size = count($nums);
    $left = 0;
    $right= $size - 1;

    while($left < $right) {
        $mid = $left + (($right - $left) >> 1);
        if($nums[$mid] > $nums[$mid + 1]) {
            // 下降区间，不一定有峰值
            // 左边高，说不定左边就是峰值，可能 mid 就是
            $right = $mid;
        } else {
            // 上升区间，可能有峰值
            // 右边高，说明在mid右边有峰值，
                // 如果是nums[mid] < nums[mid + 1]，那么mid肯定不是
                // 如果是nums[mid] = nums[mid + 1]，那么mid也不需要考虑
            $left = $mid + 1;
        }
    }

    // 左右指针
    return $left;

}



$nums = [2,4,1,2,7,8,4];
// left=0 right=6 mid=3 
    // nums[3] < nums[4] 上升
    // left = 3 + 1 = 4
// left=4 right=6 mid=5
    // nums[5] > num[6] 下降
    // right = 5
// left=4 right=5 mid=4
    // nums[4] < nums[5] 上升
    // left = 4 + 1 = 5
// left=5 right=5 
    // 返回
var_dump(findPeakElement($nums));