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

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

方法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 协议》,转载必须注明作者和本文链接
明天我们吃什么 悲哀藏在现实中 Tacks
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!