852. 山脉数组的峰顶索引

题目描述：

符合下列属性的数组 arr 称为 山脉数组 ：

• arr.length >= 3
• 存在 i（0 < i < arr.length - 1）使得：
  • arr[0] < arr[1] < … arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > … > arr[arr.length - 1]

给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

示例 1：

输入：arr = [0,1,0]
输出：1

示例 2：

输入：arr = [0,2,1,0]
输出：1

示例 3：

输入：arr = [0,10,5,2]
输出：1

提示：

• 3 <= arr.length <= 105
• 0 <= arr[i] <= 106
• 题目数据保证 arr 是一个山脉数组

---

解题分析及思路：

思路：

使用二分查找的思路，可以让复杂度降低到 O(logN)。

• 如果 arr[mid-1] < arr[mid] > arr[mid+1]，那么 mid 就是峰顶索引。
• 如果 arr[mid-1] > arr[mid]，那么峰顶索引在左侧。
• 如果 arr[mid] < arr[mid+1]，那么峰顶索引在右侧。

func peakIndexInMountainArray(arr []int) int {
	var left, right = 0, len(arr)
	for left < right {
		var mid = left + (right-left)>>1
		if mid-1 >= 0 && mid+1 < len(arr) && arr[mid-1] < arr[mid] && arr[mid] > arr[mid+1] {
			return mid
		}
		if mid-1 >= 0 && arr[mid-1] > arr[mid] {
			right = mid - 1
		}
		if mid+1 < len(arr) && arr[mid] < arr[mid+1] {
			left = mid + 1
		}
	}
	return left
}

复杂度：

• 时间复杂度：O(logN)，其中 N 是 arr 的长度。
• 空间复杂度：O(1)，只使用常数额外空间。

执行结果：

• 执行耗时:69 ms,击败了87.65% 的Go用户
• 内存消耗:7.6 MB,击败了95.88% 的Go用户