Hard

题目描述

（这是一个交互式问题。）

回想一下，如果数组 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]

给你一个山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) == target 最小的下标 index 值。

如果不存在这样的下标 index，就请返回 -1。

何为山脉数组？如果数组 A 是一个山脉数组，那么它满足如下条件：

首先，A.length >= 3

其次，在 0 < i < A.length - 1 条件下，存在 i 使得：

  • A[0] < A[1] < ... A[i-1] < A[i]
  • A[i] > A[i+1] > ... > A[A.length - 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() <= 10^4
  • 0 <= target <= 10^9
  • 0 <= mountainArr.get(index) <= 10^9

解题思路

这是一道经典的二分查找问题，需要分三步解决：

解题思路

第一步：找到山脉的峰顶 使用二分查找找到山脉数组的峰顶位置。对于任意位置 mid，通过比较 mountainArr.get(mid) 和 mountainArr.get(mid + 1) 的大小关系来判断峰顶在左边还是右边。

第二步：在左侧上升部分查找目标值 在 [0, peak] 范围内使用标准的二分查找，因为这部分是严格递增的。如果找到目标值，由于我们要返回最小索引，直接返回。

第三步：在右侧下降部分查找目标值 只有在左侧没找到的情况下，才在 [peak, length-1] 范围内查找。这部分是严格递减的，需要调整比较逻辑。

优化策略

  • 由于题目要求返回最小索引，我们优先在左半部分查找
  • 严格控制 API 调用次数，确保不超过 100 次
  • 使用标准的二分查找模板，避免边界错误

整个算法的时间复杂度为 O(log n)，空间复杂度为 O(1)，且 API 调用次数不会超过 3 * log n 次。

代码实现

class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int n = mountainArr.length();
        
        // 第一步：找到峰顶
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int peak = left;
        
        // 第二步：在左侧上升部分查找
        left = 0, right = peak;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = mountainArr.get(mid);
            if (val == target) {
                return mid;
            } else if (val < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        // 第三步：在右侧下降部分查找
        left = peak, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = mountainArr.get(mid);
            if (val == target) {
                return mid;
            } else if (val > target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
};

class Solution:
    def findInMountainArray(self, target: int, mountainArr: 'MountainArray') -> int:
        n = mountainArr.length()
        
        # 第一步：找到峰顶
        left, right = 0, n - 1
        while left < right:
            mid = left + (right - left) // 2
            if mountainArr.get(mid) < mountainArr.get(mid + 1):
                left = mid + 1
            else:
                right = mid
        peak = left
        
        # 第二步：在左侧上升部分查找
        left, right = 0, peak
        while left <= right:
            mid = left + (right - left) // 2
            val = mountainArr.get(mid)
            if val == target:
                return mid
            elif val < target:
                left = mid + 1
            else:
                right = mid - 1
        
        # 第三步：在右侧下降部分查找
        left, right = peak, n - 1
        while left <= right:
            mid = left + (right - left) // 2
            val = mountainArr.get(mid)
            if val == target:
                return mid
            elif val > target:
                left = mid + 1
            else:
                right = mid - 1
        
        return -1

public class Solution {
    public int FindInMountainArray(int target, MountainArray mountainArr) {
        int n = mountainArr.Length();
        
        // 第一步：找到峰顶
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mountainArr.Get(mid) < mountainArr.Get(mid + 1)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int peak = left;
        
        // 第二步：在左侧上升部分查找
        left = 0; right = peak;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = mountainArr.Get(mid);
            if (val == target) {
                return mid;
            } else if (val < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        // 第三步：在右侧下降部分查找
        left = peak; right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = mountainArr.Get(mid);
            if (val == target) {
                return mid;
            } else if (val > target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
}

var findInMountainArray = function(target, mountainArr) {
    const n = mountainArr.length();
    
    // Find peak index
    let left = 0, right = n - 1;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    const peak = left;
    
    // Binary search in ascending part
    left = 0;
    right = peak;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const val = mountainArr.get(mid);
        if (val === target) {
            return mid;
        } else if (val < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    // Binary search in descending part
    left = peak;
    right = n - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const val = mountainArr.get(mid);
        if (val === target) {
            return mid;
        } else if (val > target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(log n)
空间复杂度O(1)

相关题目