当前位置：首页 > article >正文

LeetCode讲解篇之852. 山脉数组的峰顶索引

article 2024/10/8 20:18:19

文章目录

题目描述
题解思路
题解代码
题目链接

题目描述

在这里插入图片描述

题解思路

我们可以采用二分查找，每次查询区间中点元素与中点下一个元素比较

如果中点元素大于其下一个元素，则表示从中点开始向右是递减趋势，那峰值索引一定小于等于中点，我们可以舍弃中点元素后面的区间
如果中点元素小于其下一个元素，则表示从中点开始向右是递增趋势，那峰值一定大于中点，我们舍弃中点即中点前面的区间

题解代码

func peakIndexInMountainArray(arr []int) int {
    l, r := 0, len(arr) - 1
    ans := 0
    for l <= r {
        m := (l + r) >> 1
        if arr[m] > arr[m + 1] { // m + 1不可能越界，只有当arr元素从左到右不递减才会使m + 1越界，但是题目中说了保证arr是山脉数组，也就是数组元素是先上升后下降的
	        // 递减趋势，说明峰顶索引小于等于m
            ans = m
            r = m - 1
        } else {
        	// 递增趋势，说明峰顶索引大于等于m + 1
            l = m + 1
        }
    }

    return ans
}