LeetCode 题解工作台
山脉数组中查找目标值
（这是一个 交互式问题 ） 你可以将一个数组 arr 称为 山脉数组 当且仅当： arr.length >= 3 存在一些 0 的 i 使得： arr[0] arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 给定一个山脉数组 mountainArr ，返…
3
题型
6
代码语言
3
相关题
当前训练重点
困难 · 二分·搜索·答案·空间
答案摘要
我们先通过二分查找，找到数组中的最大值所在的下标 ，那么数组就可以被分成两段，前半段是递增的，后半段是递减的。 然后我们在前半段中使用二分查找，查找目标值所在的下标，如果找不到，再在后半段中使用二分查找，查找目标值所在的下标。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
（这是一个 交互式问题 ）
你可以将一个数组 arr 称为 山脉数组 当且仅当：
arr.length >= 3- 存在一些
0 < i < arr.length - 1的i使得：arr[0] < arr[1] < ... < arr[i - 1] < arr[i]arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
给定一个山脉数组 mountainArr ，返回 最小 的 index 使得 mountainArr.get(index) == target。如果不存在这样的 index，返回 -1 。
你无法直接访问山脉数组。你只能使用 MountainArray 接口来访问数组：
MountainArray.get(k)返回数组中下标为k的元素（从 0 开始）。MountainArray.length()返回数组的长度。
调用 MountainArray.get 超过 100 次的提交会被判定为错误答案。此外，任何试图绕过在线评测的解决方案都将导致取消资格。
示例 1：
输入：mountainArr = [1,2,3,4,5,3,1], target = 3 输出：2 解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。
示例 2：
输入：mountainArr = [0,1,2,4,2,1], target = 3 输出：-1 解释：3 在数组中没有出现，返回 -1。
提示：
3 <= mountainArr.length() <= 1040 <= target <= 1090 <= mountainArr.get(index) <= 109
解题思路
方法一：二分查找
我们先通过二分查找，找到数组中的最大值所在的下标 ，那么数组就可以被分成两段，前半段是递增的，后半段是递减的。
然后我们在前半段中使用二分查找，查找目标值所在的下标，如果找不到，再在后半段中使用二分查找，查找目标值所在的下标。
时间复杂度 ，其中 是数组的长度。空间复杂度 。
# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
# class MountainArray:
# def get(self, index: int) -> int:
# def length(self) -> int:
class Solution:
def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
def search(l: int, r: int, k: int) -> int:
while l < r:
mid = (l + r) >> 1
if k * mountain_arr.get(mid) >= k * target:
r = mid
else:
l = mid + 1
return -1 if mountain_arr.get(l) != target else l
n = mountain_arr.length()
l, r = 0, n - 1
while l < r:
mid = (l + r) >> 1
if mountain_arr.get(mid) > mountain_arr.get(mid + 1):
r = mid
else:
l = mid + 1
ans = search(0, l, 1)
return search(l + 1, n - 1, -1) if ans == -1 else ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(log N) for each binary search step, first for peak identification, then for ascending and descending searches. Space complexity is O(log N) due to recursion stack or iterative binary search bookkeeping. |
| 空间 | O(\log N) |
面试官常问的追问
外企场景- question_mark
Expect candidates to identify the mountain property and apply binary search.
- question_mark
Look for handling of interactive constraints and minimal array accesses.
- question_mark
Assess understanding of searching both ascending and descending segments separately.
常见陷阱
外企场景- error
Failing to find the true peak before searching both sides.
- error
Applying standard binary search without adjusting for descending portion.
- error
Exceeding interactive call limits by redundant get() requests.
进阶变体
外企场景- arrow_right_alt
Find the maximum element in a mountain array without a target search.
- arrow_right_alt
Locate multiple targets in a mountain array and return all indices efficiently.
- arrow_right_alt
Determine if a value exists anywhere in the array with minimal get() calls.