LeetCode讲解篇之852. 山脉数组的峰顶索引
题目描述
题解思路
我们可以采用二分查找，每次查询区间中点元素与中点下一个元素比较
- 如果中点元素大于其下一个元素，则表示从中点开始向右是递减趋势，那峰值索引一定小于等于中点，我们可以舍弃中点元素后面的区间
- 如果中点元素小于其下一个元素，则表示从中点开始向右是递增趋势，那峰值一定大于中点，我们舍弃中点即中点前面的区间
题解代码
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
}
题目链接
https://leetcode.cn/problems/peak-index-in-a-mountain-array/description/
原文地址：https://blog.csdn.net/qq_67733273/article/details/142735828
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！