1095. 山脉数组中查找目标值

给你一个 山脉数组 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:

输入:array = [1,2,3,4,5,3,1], target = 3
输出:2
解释:3 在数组中出现了两次,下标分别为 2 和 5,我们返回最小的下标 2。

示例 2:

输入:array = [0,1,2,4,2,1], target = 3
输出:-1
解释:3 在数组中没有出现,返回 -1。

提示:

3 <= mountain_arr.length() <= 10000
0 <= target <= 10^9
0 <= mountain_arr.get(index) <= 10^9

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-in-mountain-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路及算法

通过峰值元素,可以将原数组在逻辑上一分为二,分出来的两个子数组分别有序。

然后分别对 左边子数组 和 右边子数组 进行查找即可,两个数组均不满足则返回 -1

查找峰值元素

通过题目了解和直观的判断,我们可以知道 当一个数既大于左邻居数又大于右邻居数时,这个数就是峰值元素

于是乎,我们可以使用二分查找的方法找到 峰值元素

def find_peak_index(left, right):
	while left + 1 < right:
        mid = (left + right) >> 1
        x = mountain_arr.get(mid) 		# 中间元素
        y = mountain_arr.get(mid+1)		# 右邻居元素
        z = mountain_arr.get(mid-1)		# 左邻居元素
        if x > y and x > z:
            # 找到峰值
            return mid
        elif y >= x >= z:
            left = mid
        elif y <= x <= z:
            right = mid

因为两个子数组有着明显差异,一个升序,一个降序,所以收缩边界的条件可以进行优化

  • 当mid位置的元素大于右邻居元素时 arr[mid] > arr[mid + 1]

mid落在了降序的子数组中,峰值在其左侧,所以收缩右边界 right = mid,因为当前 mid 的值刚好可能是峰值,所以这里就不 +1

  • 反面 arr[mid] <= arr[mid + 1]

mid落在了升序的子数组中,峰值在其右侧,所以收缩左边界 left = mid + 1,因为 mid 小于右邻居元素,所以它不可能是峰值元素,所以这里可以 +1

def find_peak_index(left, right):
	while left < right:
        mid = (left + right) >> 1
        if mountain_arr.get(mid) > mountain_arr.get(mid + 1):
            right = mid
		else:
            left = mid + 1
    return left

查找target元素

如果存在重复元素,按题目要求应该返回索引值较小的,所以我们先查找升序数组。

这一步依然是使用二分查找

        def binary_search(left, right, v):
            while left <= right:
                mid = (left + right) >> 1
                mid_value = mountain_arr.get(mid)
                if mid_value < target:
                    if v:
                        left = mid + 1
                    else:
                        right = mid - 1
                elif mid_value > target:
                    if v:
                        right = mid - 1
                    else:
                        left = mid + 1
                else:
                    return mid
            return -1

为了减少代码量,使升序数组和降序数组都可以使用,则新增一个布尔值,用于判断当前数组是升序还是降序

完整代码

# """
# 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:
        # nums[i] > nums[i+1] 表示i是峰值元素
        size = mountain_arr.length()
        left = 0
        right = size - 1

        def find_peak_index(left, right):
            while left + 1 < right:
                mid = (left + right) >> 1
                if mountain_arr.get(mid) > mountain_arr.get(mid + 1):
                    right = mid
                else:
                    left = mid + 1
            return right
        
        def binary_search(left, right, v):
            while left <= right:
                mid = (left + right) >> 1
                mid_value = mountain_arr.get(mid)
                if mid_value < target:
                    if v:
                        left = mid + 1
                    else:
                        right = mid - 1
                elif mid_value > target:
                    if v:
                        right = mid - 1
                    else:
                        left = mid + 1
                else:
                    return mid
            return -1
        
        peak = find_peak_index(left, right)
        l = binary_search(left, peak, True)
        if l != -1: return l
        r = binary_search(peak+1, right, False)
        return r if r != -1 else -1