跳至主要內容

0852. 山脉数组的峰顶索引

ITCharge大约 1 分钟

0852. 山脉数组的峰顶索引open in new window

  • 标签:数组、二分查找
  • 难度:中等

题目链接

题目大意

描述:给定由整数组成的山脉数组 arrarr

要求:返回任何满足 $arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[len(arr) - 1] $ 的下标 ii

说明

  • 山脉数组:满足以下属性的数组:
    1. len(arr)3len(arr) \ge 3
    2. 存在 ii0<i<len(arr)10 < i < len(arr) - 1),使得:
      1. arr[0]<arr[1]<...arr[i1]<arr[i]arr[0] < arr[1] < ... arr[i-1] < arr[i]
      2. arr[i]>arr[i+1]>...>arr[len(arr)1]arr[i] > arr[i+1] > ... > arr[len(arr) - 1]
  • 3<=arr.length<=1053 <= arr.length <= 105
  • 0<=arr[i]<=1060 <= arr[i] <= 106
  • 题目数据保证 arrarr 是一个山脉数组

示例

  • 示例 1:
输入:arr = [0,1,0]
输出:1
  • 示例 2:
输入:arr = [0,2,1,0]
输出:1

解题思路

思路 1:二分查找

  1. 使用两个指针 leftleftrightrightleftleft 指向数组第一个元素,rightright 指向数组最后一个元素。
  2. 取区间中间节点 midmid,并比较 nums[mid]nums[mid]nums[mid+1]nums[mid + 1] 的值大小。
    1. 如果 nums[mid]<nums[mid+1]nums[mid]< nums[mid + 1],则右侧存在峰值,令 left = mid + 1
    2. 如果 nums[mid]nums[mid+1]nums[mid] \ge nums[mid + 1],则左侧存在峰值,令 right = mid
  3. 最后,当 left==rightleft == right 时,跳出循环,返回 leftleft

思路 1:代码

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left = 0
        right = len(arr) - 1
        while left < right:
            mid = left + (right - left) // 2
            if arr[mid] < arr[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return left

思路 1:复杂度分析

  • 时间复杂度O(logn)O(\log n)
  • 空间复杂度O(1)O(1)