LeetCode 题解工作台
山脉数组的峰顶索引
给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。 返回峰值元素的下标。 你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。 示例 1： 输入： arr = [0,1,0] 输出： 1 示例 2： 输入： arr = [0,2,1,0] 输出： 1…
2
题型
7
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
class Solution: def peakIndexInMountainArray(self, arr: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。
返回峰值元素的下标。
你必须设计并实现时间复杂度为 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 <= 1050 <= arr[i] <= 106- 题目数据 保证
arr是一个山脉数组
解题思路
方法一
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
left, right = 1, len(arr) - 2
while left < right:
mid = (left + right) >> 1
if arr[mid] > arr[mid + 1]:
right = mid
else:
left = mid + 1
return left
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(\log n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
The candidate effectively applies binary search to reduce the problem size at each step.
- question_mark
The solution minimizes time complexity, showing understanding of O(log n) algorithms.
- question_mark
The candidate considers edge cases and correctly narrows the search space.
常见陷阱
外企场景- error
Misunderstanding the search direction: always ensure the search space is narrowed toward the correct half (left or right) based on comparisons.
- error
Forgetting to check both neighbors of the middle element before concluding that it is the peak.
- error
Handling arrays with fewer than 3 elements incorrectly, even though the problem guarantees a valid mountain array.
进阶变体
外企场景- arrow_right_alt
What if the mountain array was allowed to contain equal adjacent elements? Would binary search still work?
- arrow_right_alt
Can the solution be adapted for an unsorted array?
- arrow_right_alt
How would the approach change if the peak element could be at the ends of the array?