《LeetCode 力扣》 - 852. 山脉数组的峰顶索引 (暴力/二分)

• ref
  • 852. 山脉数组的峰顶索引
• contact
  • 顺丰同城算法题

方法1 暴力

class Solution {

    /**
     * @param Integer[] $arr
     * @return Integer
     */
    function peakIndexInMountainArray($arr) {
        $size = count($arr);
        $ans = -1;
        for($i = 0; $i <= $size - 2; $i++) {
            if($arr[$i] > $arr[$i+1]) {
                $ans = $i;
                break;
            }
        }
        return $ans;
    }
}

方法2 二分法

写法1 $left <= $right

• 循环里面判断峰值
• 循环体内有3个分支
• 出循环
  • 1）left > right
  • 2）或者找到峰值

class Solution {

    /**
     * @param Integer[] $arr
     * @return Integer
     */
    function peakIndexInMountainArray($arr) {
        $size = count($arr);
        $ans = -1;

        $left = 0;
        $right= $size - 1;

        while($left <= $right) {
            $mid = $left + (($right - $left) >> 1);
            if($mid + 1 > $size - 1) {
                break;
            }
            if($arr[$mid] > $arr[$mid+1] && $arr[$mid] > $arr[$mid-1]) {
                $ans = $mid;
                break;
            } elseif($arr[$mid+1] >= $arr[$mid]) {
                $left = $mid + 1;
            } else {
                $right= $mid;
            }
        }
        return $ans;
    }
}

写法2 $left < $right

• 循环体内有2个分支
• 循环体外返回目标索引，在循环体内缩减搜索区间
• 出循环
  • 当 left == right ，然后判断峰值的位置，如果是最后一位则不是峰顶

class Solution {

    /**
     * @param Integer[] $arr
     * @return Integer
     */
    function peakIndexInMountainArray($arr) {
        $size = count($arr);
        $ans = -1;

        $left = 0;
        $right= $size - 1;

        while($left < $right) {
            $mid = $left + (($right - $left) >> 1);
            if($mid + 1 > $size - 1) {
                break;
            }
            if($arr[$mid+1] >= $arr[$mid]) {
                $left = $mid + 1;
            } else {
                $right= $mid;
            }
        }
        if($left != $size - 1) {
            $ans = $left;
        }
        return $ans;
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接